Optimum Branchings: The Vertices of the Branching Polyhedron Are Exactly the BranchingsResearch Paper
A branching in a directed graph is a set of edges that contains no cycle (even ignoring directions) and in which no two edges point to the same node; a connected branching is an arborescence, a tree rooted at one node with all edges directed away from the root. The optimum branching problem asks, for real weights on the edges, for a branching of maximum…