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

DOI10.1016/j.tcs.2012.06.024zbMath1251.05137MaRDI 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\)-factor; graph matching; \(b\)-matching; blossom

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C22: Signed and weighted graphs

Related Items

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