Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers
From MaRDI portal
Publication:2149100
DOI10.1007/s00453-022-00949-5zbMath1492.68144arXiv1706.05761OpenAlexW4214659657MaRDI QIDQ2149100
Publication date: 28 June 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.05761
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Blocking trails for \(f\)-factors of multigraphs ⋮ A weight-scaling algorithm for \(f\)-factors of multigraphs ⋮ Approximation algorithms in combinatorial scientific computing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple approximation algorithm for the weighted matching problem
- A linear-time algorithm for a special case of disjoint set union
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- Linear-Time Approximation for Maximum Weight Matching
- On the Problem of Decomposing a Graph into n Connected Factors
- A Greedy Heuristic for the Set-Covering Problem
- Efficiency of a Good But Not Linear Set Union Algorithm
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- 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
- Faster Scaling Algorithms for Network Problems
- Paths, Trees, and Flowers
- Maximum matching and a polyhedron with 0,1-vertices
