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

DOI10.1016/J.TCS.2012.06.024zbMATH Open1251.05137OpenAlexW2066470474MaRDI QIDQ714819FDOQ714819

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

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

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)

Cites Work

• Title not available (Why is that?)
• Matching theory
• Paths, Trees, and Flowers
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Maximum matching and a polyhedron with 0,1-vertices
• Maximum weight bipartite matching in matrix multiplication time
• 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
• Matching is as easy as matrix inversion
• Title not available (Why is that?)
• Title not available (Why is that?)
• An algebraic algorithm for weighted linear matroid intersection
• Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings

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)