Data Reduction for Maximum Matching on Real-World Graphs
DOI10.1145/3439801zbMath1499.68279OpenAlexW3158251097MaRDI QIDQ5102046
Rolf Niedermeier, André Nichterlein, Tomohiro Koana, Philipp Zschoche, Viatcheslav Korenwein
Publication date: 6 September 2022
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3439801
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Blossom V: A new implementation of a minimum cost perfect matching algorithm
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
- Matching is as easy as matrix inversion
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- The power of linear-time data reduction for maximum matching
- On the König deficiency of zero-reducible graphs
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Crown structures for vertex cover kernelization
- Crown reductions for the minimum weighted vertex cover problem
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Linear-Time Approximation for Maximum Weight Matching
- On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
- Vertex packings: Structural properties and algorithms
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
- Scaling Algorithms for Weighted Matching in General Graphs
- Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
- Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
- Karp-Sipser based kernels for bipartite graph matching
- Paths, Trees, and Flowers
- Linear-Time FPT Algorithms via Network Flow
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- Maximum matching and a polyhedron with 0,1-vertices
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Graph-Theoretic Concepts in Computer Science
- Combinatorial optimization. Theory and algorithms
This page was built for publication: Data Reduction for Maximum Matching on Real-World Graphs
