A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors

DOI10.1016/j.tcs.2012.06.024zbMath1251.05137OpenAlexW2066470474MaRDI QIDQ714819

Harold N. Gabow

Publication date: 11 October 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.024

zbMATH Keywords

dual variables\(f\)-factorgraph matching\(b\)-matchingblossom

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Signed and weighted graphs (05C22)

Related Items (3)

NC Algorithms for Weighted Planar Perfect Matching and Related Problems ⋮ Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors ⋮ Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths

Cites Work

• Maximum weight bipartite matching in matrix multiplication time
• Matching theory
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Algorithmic Applications of Baur-Strassen’s Theorem
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors