The Power of Linear-Time Data Reduction for Maximum Matching
DOI10.4230/LIPIcs.MFCS.2017.46zbMath1441.68192OpenAlexW2772612740MaRDI QIDQ5111261
André Nichterlein, George B. Mertzios, Rolf Niedermeier
Publication date: 26 May 2020
Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.46
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) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (13)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- New Races in Parameterized Algorithmics
- Linear-Time Approximation for Maximum Weight Matching
- 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
- A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- Kernelization Lower Bounds by Cross-Composition
- Parameterized and Exact Computation
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- 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