Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths

DOI10.1137/16M1106225zbMath1461.05212OpenAlexW3151200418MaRDI QIDQ5858647

Piotr Sankowski, Harold N. Gabow

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/16m1106225

zbMATH Keywords

matchingsshortest pathsfactorsalgebraic algorithms

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors
• A linear-time algorithm for a special case of disjoint set union
• Undirected distances and the postman-structure of graphs
• Maintaining bridge-connected and biconnected components on-line
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On a routing problem
• Powers of tensors and fast matrix multiplication
• On Finding Lowest Common Ancestors in Trees
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Faster scaling algorithms for general graph matching problems
• Potentials in Undirected Graphs and Planar Multiflows
• Data Structures for Weighted Matching and Extensions to b -matching and f -factors
• Scaling Algorithms for Weighted Matching in General Graphs
• Algorithms – ESA 2005
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths