The power of linear-time data reduction for maximum matching
type: Item
instance of: scholarly article
title: The power of linear-time data reduction for maximum matching
zbMATH Open document ID: 1492.68108
author: George B. Mertzios
author: André Nichterlein
author: Rolf Niedermeier
published in: Algorithmica
publication date: 2020-11-11T00:00:00Z
full work available at URL: https://arxiv.org/abs/1609.08879
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 7272772
zbMATH Keywords: maximum-cardinality matching
zbMATH Keywords: bipartite graphs
zbMATH Keywords: linear-time algorithms
zbMATH Keywords: kernelization
zbMATH Keywords: parameterized complexity analysis
zbMATH Keywords: FPT in P
describes a project that uses: Stony Brook
MaRDI profile type: Publication
OpenAlex ID: W3104783836
arXiv ID: 1609.08879
cites work: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
cites work: Q3418606
cites work: Q4038720
cites work: Graph Classes: A Survey
cites work: Parameterized complexity of vertex colouring
cites work: Matching and multidimensional matching in chordal and strongly chordal graphs
cites work: Linear-Time Approximation for Maximum Weight Matching
cites work: Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: Faster scaling algorithms for general graph matching problems
cites work: Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
cites work: Parameterized and Exact Computation
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
cites work: Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
cites work: Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
cites work: A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
cites work: Algorithms – ESA 2004
cites work: Sparsity. Graphs, structures, and algorithms
cites work: A linear time algorithm for maximum matchings in convex, bipartite graphs
cites work: Maximum matching in regular and almost regular graphs
cites work: Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
DOI: 10.1007/S00453-020-00736-0
description: scientific article