A weight-scaling algorithm for \(f\)-factors of multigraphs

DOI10.1007/s00453-023-01127-xarXiv2010.01102OpenAlexW3090768320MaRDI QIDQ6046950

Harold N. Gabow

Publication date: 6 October 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.01102

zbMATH Keywords

multigraphgraphmatchingscaling\(f\)-factor\(f\)-matching

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Matching theory
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
• Applications of Path Compression on Balanced Trees
• Undirected single-source shortest paths with positive integer weights in linear time
• An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Network Flow and Testing Graph Connectivity
• Faster scaling algorithms for general graph matching problems
• Data Structures for Weighted Matching and Extensions to b -matching and f -factors
• Scaling Algorithms for Weighted Matching in General Graphs
• The Weighted Matching Approach to Maximum Cardinality Matching
• Faster Scaling Algorithms for Network Problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• Maximum matching and a polyhedron with 0,1-vertices
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Minimum cost flows, MDPs, and ℓ ₁ -regression in nearly linear time for dense instances

This page was built for publication: A weight-scaling algorithm for \(f\)-factors of multigraphs