The Power of Linear-Time Data Reduction for Maximum Matching
DOI10.4230/LIPICS.MFCS.2017.46zbMATH Open1441.68192OpenAlexW2772612740MaRDI QIDQ5111261FDOQ5111261
Authors: George B. Mertzios, André Nichterlein, Rolf Niedermeier 
Publication date: 26 May 2020
Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.46
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
bipartite graphskernelizationlinear-time algorithmsparameterized complexity analysisFPT in Pmaximum-cardinality matching
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- The algorithm design manual
- Graph Classes: A Survey
- Faster scaling algorithms for general graph matching problems
- Algorithms – ESA 2004
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- A linear-time algorithm for a special case of disjoint set union
- Linear-Time Approximation for Maximum Weight Matching
- Kernelization Lower Bounds by Cross-Composition
- Parameterized and Exact Computation
- Parameterized complexity of vertex colouring
- New races in parameterized algorithmics
- Title not available (Why is that?)
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Maximum matching in regular and almost regular graphs
- Matching and multidimensional matching in chordal and strongly chordal graphs
- A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
Cited In (15)
- Linear-time parameterized algorithms with limited local resources
- Data Reduction for Maximum Matching on Real-World Graphs
- When can graph hyperbolicity be computed in linear time?
- Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
- A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
- The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
- Getting linear time in graphs of bounded neighborhood diversity
- Temporal matching
- Computing maximum matchings in temporal graphs
- Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
- Maximum matching in almost linear time on graphs of bounded clique-width
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
- Parameterized aspects of triangle enumeration
Uses Software
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 Q5111261)
