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