A simple derivation of edmonds' algorithm for optimum branchings

DOI10.1002/net.3230010305zbMath0229.05127OpenAlexW2014686215MaRDI QIDQ5636925

Richard M. Karp

Publication date: 1972

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230010305

Mathematics Subject Classification ID

Applications of graph theory (05C90) Directed graphs (digraphs), tournaments (05C20)

Related Items

Maximal dynamic polymatroid flows and applications, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, How to Sort by Walking on a Tree, Approximating Transitive Reductions for Directed Networks, Approximating the Spanning k-Tree Forest Problem, How to sort by walking and swapping on paths and trees, Ranking arborescences in O(Km log n) time, Arborescence optimization problems solvable by Edmonds' algorithm, Unnamed Item, On finding optimal polytrees, APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM, Approximating optimum branchings in linear time, Estimating an oncogenetic tree when false negatives and positives are present

Cites Work

• Optimum branchings