/Min-Cost-Arborescence

Primary LanguageC++MIT LicenseMIT

Min Cost Arborescence using Edmonds Branching Algorithm

Given a digraph G = (V. F) and a root r in V, an arborescence (rooted at r) is a subgraph T= (V. F) such that

  • T is a spanning tree of G if we ignore the direction of edges.
  • There is a directed path in T from r to each other node v E

Edmonds Branching Algorithm

image