Premium
A simple derivation of edmonds' algorithm for optimum branchings
Author(s) -
Karp R. M.
Publication year - 1971
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230010305
Subject(s) - polyhedron , correctness , mathematics , simple (philosophy) , algorithm , integer programming , branching (polymer chemistry) , combinatorial algorithms , combinatorics , discrete mathematics , philosophy , materials science , epistemology , composite material
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.