A weight-scaling algorithm for f-factors of multigraphs

DOI10.1007/S00453-023-01127-XOpenAlexW3090768320MaRDI QIDQ6046950FDOQ6046950

Authors 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

graphmultigraphmatchingscaling\(f\)-factor\(f\)-matching

Mathematics Subject Classification ID

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

Abstract: We discuss combinatorial algorithms for finding a maximum weight $f$-factor on an arbitrary multigraph, for given integral weights of magnitude at most $W$. For simple bipartite graphs the best-known time bound is $O(n^{2/3},m,lognW)$ (cite{GT89}; $n$ and $m$ are respectively the number of vertices and edges). A recent algorithm of Duan and He et al. cite{DHZ} for $f$-factors of simple graphs comes within logarithmic factors of this bound, $widetildeO(n^{2/3},m,logW)$. The best-known bound for bipartite multigraphs is $O(sqrtPhi,m,logPhiW)$ ($Philem$ is the size of the $f$-factor, $Phi=su{m}_{vinV}f(v)/2$). This bound is more general than the restriction to simple graphs, and is even superior on "small" simple graphs, i.e., $Phi=o(n^{4/3})$. We present an algorithm that comes within a $sqrtlogPhi$ factor of this bound, i.e., $O(sqrtPhilogPhi,m,logPhiW)$. The algorithm is a direct generalization of the algorithm of Gabow and Tarjan cite{GT} for the special case of ordinary matching ($fequiv1$). We present our algorithm first for ordinary matching, as the analysis is a simplified version of cite{GT}. Furthermore the algorithm and analysis both get incorporated without modification into the multigraph algorithm. To extend these ideas to $f$-factors, the first step is "expanding" edges (i.e., replacing an edge by a length 3 alternating path). cite{DHZ} uses a one-time expansion of the entire graph. Our algorithm keeps the graph small by only expanding selected edges, and "compressing" them back to their original source when no longer needed. Several other ideas are needed, including a relaxation of the notion of "blossom" to e-blossom ("expanded blossom").

Cites work

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046950)