A simple derivation of edmonds' algorithm for optimum branchings

@article{karp72, abstract = {Edmonds [1] has given an algorithm for constructing a maximum-weight branching in a weighted directed graph. His proof that the algorithm is correct is based on linear programming theory, and establishes as a by-product that a certain polyhedron has integer vertices. Here we give a direct combinatorial proof of the correctness of the algorithm.}, address = {Department of Computer Science University of California Berkeley, California}, author = {Karp, R. M. }, citeulike-article-id = {2997344}, doi = {http://dx.doi.org/10.1002/net.3230010305}, journal = {Networks}, keywords = {dmst, mst}, number = {3}, pages = {265--272}, posted-at = {2008-07-13 15:52:51}, priority = {2}, title = {A simple derivation of edmonds' algorithm for optimum branchings}, url = {http://dx.doi.org/10.1002/net.3230010305}, volume = {1}, year = {1971} }

TY - JOUR ID - karp72 L3 - citeulike-article-id:2997344 TI - A simple derivation of edmonds' algorithm for optimum branchings JF - Networks VL - 1 IS - 3 SP - 265 EP - 272 AD - Department of Computer Science University of California Berkeley, California N2 - Edmonds [1] has given an algorithm for constructing a maximum-weight branching in a weighted directed graph. His proof that the algorithm is correct is based on linear programming theory, and establishes as a by-product that a certain polyhedron has integer vertices. Here we give a direct combinatorial proof of the correctness of the algorithm. KW - dmst KW - mst AU - Karp, RM PY - 1971/// UR - http://dx.doi.org/10.1002/net.3230010305 ER -