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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom