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

zbMATH Keywords

bipartite graphslinear-time algorithmskernelizationparameterized complexity analysisFPT in Pmaximum-cardinality matching

Mathematics Subject Classification ID

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)

Data Reduction for Maximum Matching on Real-World Graphs ⋮ Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ An Adaptive Version of Brandes' Algorithm for Betweenness Centrality ⋮ A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph ⋮ Parameterized complexity of diameter ⋮ Reflections on kernelizing and computing unrooted agreement forests

Uses Software

• Stony Brook

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