The power of linear-time data reduction for maximum matching
From MaRDI portal
Publication:2211355
Abstract: Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For -edge and -vertex graphs, it is well-known to be solvable in time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on (almost) linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.
Recommendations
- The Power of Linear-Time Data Reduction for Maximum Matching
- Data Reduction for Maximum Matching on Real-World Graphs
- Linear-time approximation for maximum weight matching
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
Cites work
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- A linear-time algorithm for a special case of disjoint set union
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
- Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
- Algorithms – ESA 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
- Deterministic soliton graphs
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- Faster scaling algorithms for general graph matching problems
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- Graph Classes: A Survey
- scientific article; zbMATH DE number 177842 (Why is no real title available?)
- Linear-time approximation for maximum weight matching
- Matching and multidimensional matching in chordal and strongly chordal graphs
- Maximum matching in regular and almost regular graphs
- On the power of tree-depth for fully polynomial FPT algorithms
- Parameterized and Exact Computation
- Parameterized complexity of vertex colouring
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Sparsity. Graphs, structures, and algorithms
Cited in
(12)- A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph
- Reflections on kernelizing and computing unrooted agreement forests
- Linear-time parameterized algorithms with limited local resources
- Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
- Data Reduction for Maximum Matching on Real-World Graphs
- The Power of Linear-Time Data Reduction for Maximum Matching
- An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
- Parameterized complexity of diameter
- Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
- Backdoor DNFs
- Effective data reduction for strongly stable matching in very sparse graphs
- Fast convolutions for near-convex sequences
This page was built for publication: The power of linear-time data reduction for maximum matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2211355)
