The Power of Linear-Time Data Reduction for Maximum Matching
From MaRDI portal
(Redirected from Publication:5111261)
bipartite graphsFPT in Pkernelizationlinear-time algorithmsmaximum-cardinality matchingparameterized complexity analysis
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
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 – ESA 2004
- Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
- 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
- scientific article; zbMATH DE number 177842 (Why is no real title available?)
- 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)- Maximum matching in almost linear time on graphs of bounded clique-width
- Linear-time parameterized algorithms with limited local resources
- The power of linear-time data reduction for maximum matching
- The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
- Temporal matching
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
- Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
- The \(b\)-matching problem in distance-hereditary graphs and beyond
- On adaptive algorithms for maximum matching
- Data Reduction for Maximum Matching on Real-World Graphs
- When can graph hyperbolicity be computed in linear time?
- Computing maximum matchings in temporal graphs
- Getting linear time in graphs of bounded neighborhood diversity
- Effective data reduction for strongly stable matching in very sparse 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)
