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 (13)

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

This page was built for publication: A simple derivation of edmonds' algorithm for optimum branchings