Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors

DOI10.1137/16M1106195zbMath1461.05211OpenAlexW3142718897MaRDI QIDQ5858644

Harold N. Gabow, Piotr Sankowski

Publication date: 14 April 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1106195

zbMATH Keywords

matchingsshortest pathsfactorsalgebraic algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (1)

Maximum matching in almost linear time on graphs of bounded clique-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors
• Maximum weight bipartite matching in matrix multiplication time
• A polynomial algorithm for b-matchings: An alternative approach
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• High-order lifting and integrality certification
• Maximum matchings in general graphs through randomization
• Beyond the flow decomposition barrier
• Algorithmic Applications of Baur-Strassen’s Theorem
• Powers of tensors and fast matrix multiplication
• Algebraic Algorithms for Matching and Matroid Problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Faster Scaling Algorithms for Network Problems
• Algorithms – ESA 2004
• Graph Connectivities, Network Coding, and Expander Graphs
• Max flows in O(nm) time, or better
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors