The Power of Linear-Time Data Reduction for Maximum Matching
From MaRDI portal
Publication:5111261
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)
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
- scientific article; zbMATH DE number 177842 (Why is no real title available?)
- 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
- Faster scaling algorithms for general graph matching problems
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- Graph Classes: A Survey
- Kernelization Lower Bounds by Cross-Composition
- 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
- New races in parameterized algorithmics
- Parameterized and Exact Computation
- Parameterized complexity of vertex colouring
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- The algorithm design manual
Cited in
(16)- The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
- Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
- On adaptive algorithms for maximum matching
- Temporal matching
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
- Getting linear time in graphs of bounded neighborhood diversity
- Linear-time parameterized algorithms with limited local resources
- Maximum matching in almost linear time on graphs of bounded clique-width
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- When can graph hyperbolicity be computed in linear time?
- Data Reduction for Maximum Matching on Real-World Graphs
- Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
- The power of linear-time data reduction for maximum matching
- Effective data reduction for strongly stable matching in very sparse graphs
- scientific article; zbMATH DE number 7561384 (Why is no real title available?)
- Computing maximum matchings in temporal graphs
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)
