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

DOI10.1016/J.TCS.2012.06.024MaRDI QIDQ714819zbMATH OpenOpenAlexFDO

Authors 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

graph matching\(b\)-matching\(f\)-factorblossomdual variables

Mathematics Subject Classification ID

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

Recommendations

• An algorithmic approach to dual integrality of matching and extensions
• On dual integrality in matching problems
• A weighted independent even factor algorithm
• Total dual integrality of matching forest constraints
• Optimum matchings in weighted bipartite graphs

Cites work

• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3637616 (Why is no real title available?)
• scientific article; zbMATH DE number 3437188 (Why is no real title available?)
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings
• An algebraic algorithm for weighted linear matroid intersection
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Constructing a perfect matching is in random NC
• Matching is as easy as matrix inversion
• Matching theory
• Maximum matching and a polyhedron with 0,1-vertices
• Maximum weight bipartite matching in matrix multiplication time
• Paths, Trees, and Flowers

Cited in

(3)

• Algorithms for weighted matching generalizations. II: \(f\)-factors and the special case of shortest paths
• NC algorithms for weighted planar perfect matching and related problems
• Algorithms for weighted matching generalizations. I: Bipartite graphs, \(b\)-matching, and unweighted \(f\)-factors

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714819)