The power of linear-time data reduction for maximum matching
DOI10.1007/s00453-020-00736-0zbMath1492.68108arXiv1609.08879OpenAlexW3104783836MaRDI QIDQ2211355
George B. Mertzios, André Nichterlein, Rolf Niedermeier
Publication date: 11 November 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1609.08879
bipartite graphslinear-time algorithmskernelizationparameterized complexity analysisFPT in Pmaximum-cardinality matching
Analysis of algorithms (68W40) 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 (6)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- A linear-time algorithm for a special case of disjoint set union
- Matching and multidimensional matching in chordal and strongly chordal graphs
- Parameterized complexity of vertex colouring
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- Maximum matching in regular and almost regular graphs
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Linear-Time Approximation for Maximum Weight Matching
- On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Graph Classes: A Survey
- Faster scaling algorithms for general graph matching problems
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
- A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
- Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- Parameterized and Exact Computation
- Algorithms – ESA 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: The power of linear-time data reduction for maximum matching