Blocking trails for f-factors of multigraphs

DOI10.1007/S00453-023-01126-YarXiv2112.04096OpenAlexW4376505282MaRDI QIDQ6046949FDOQ6046949

Authors: Harold N. Gabow 

Publication date: 6 October 2023

Published in: Algorithmica (Search for Journal in Brave)

Abstract: Blocking flows, introduced by Dinic [2] for network flow, have been used to speed up many augmenting-path type algorithms, especially matching algorithms e.g., [18, 23, 16]. We present an $O(m)$ time algorithm for blocking trails for f-factors of general multigraphs. This improves a previous algorithm by a factor of $alpha(m,n)$. This speeds up a number of efficient algorithms for f-factors, e.g., the algorithm of [11] for maximum weight f-matching improves by the aforementioned $alpha(m,n)$ factor to running time $O(sqrtPhilogPhimlog(PhiW))$ for $Phi=su{m}_{vinV}f(v)$, $W$ the maximum edge weight. This time bound is within a factor $sqrtlogPhi$ of the bound for bipartite multigraphs. The technical difficulty for this work stems from the fact that previous algorithms for both matching and $f$-matching use vertex contractions to form blossoms, but our dfs-based approach necessitates using edge contractions. As an example difficulty, edge contractions introduce a new form of blossoms we call "skew blossoms". These are configurations that must be reorganized in order to become valid blossoms.

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

zbMATH Keywords

graphmultigraphmatching\(f\)-factordegree-constrained subgraph\(f\)-matching

Mathematics Subject Classification ID

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

Cites Work

• Matching theory
• Paths, Trees, and Flowers
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Faster scaling algorithms for general graph matching problems
• Faster Scaling Algorithms for Network Problems
• Title not available (Why is that?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• A linear-time algorithm for a special case of disjoint set union
• Network Flow and Testing Graph Connectivity
• The weighted matching approach to maximum cardinality matching
• Data structures for weighted matching and extensions to \(b\)-matching and \(f\)-factors
• Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
• A Data Structure for Nearest Common Ancestors with Linking

This page was built for publication: Blocking trails for \(f\)-factors of multigraphs

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