A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors
From MaRDI portal
Publication:714819
DOI10.1016/j.tcs.2012.06.024zbMath1251.05137OpenAlexW2066470474MaRDI QIDQ714819
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
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