On adaptive algorithms for maximum matching

DOI10.4230/LIPICS.ICALP.2019.71MaRDI QIDQ5091230zbMATH OpenFDO

Authors Falko Hegerfeld, Stefan Kratsch

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1904.11244

zbMATH Keywords

adaptive analysismatchingsparameterized complexity

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• The general maximum matching algorithm of Micali and Vazirani
• Maximum matching in regular and almost regular graphs
• STACS 2004
• Matching algorithms are fast in sparse random graphs
• Computing large matchings fast

Cites work

• A graph‐theoretic generalization of the clique concept
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing
• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
• An O(n) time algorithm for maximum matching on cographs
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Approximation and tidying -- a problem kernel for s-plex cluster vertex deletion
• Bipartite graphs totally decomposable by canonical decomposition
• Computing graph distances parameterized by treewidth and diameter
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• Faster scaling algorithms for general graph matching problems
• Finding a maximum matching in a circular-arc graph
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• scientific article; zbMATH DE number 177842 (Why is no real title available?)
• scientific article; zbMATH DE number 1107732 (Why is no real title available?)
• scientific article; zbMATH DE number 2040948 (Why is no real title available?)
• scientific article; zbMATH DE number 6850484 (Why is no real title available?)
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• Matching algorithms are fast in sparse random graphs
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Matching triangles and basing hardness on an extremely popular conjecture
• Maximum matching in a convex bipartite graph
• Maximum matching in graphs with an excluded minor
• Maximum matching in regular and almost regular graphs
• Maximum skew-symmetric flows and matchings
• On compressing permutations and adaptive sorting
• On the possibility of faster \textsc{SAT} algorithms
• On the power of tree-depth for fully polynomial FPT algorithms
• Paths, Trees, and Flowers
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Robust and adaptive search
• Sparsity. Graphs, structures, and algorithms
• The Power of Linear-Time Data Reduction for Maximum Matching
• TWO THEOREMS IN GRAPH THEORY
• When can graph hyperbolicity be computed in linear time?

Cited in

(3)

• Maximum matching in almost linear time on graphs of bounded clique-width
• Data Reduction for Maximum Matching on Real-World Graphs
• Dynamic Matching Algorithms in Practice

This page was built for publication: On adaptive algorithms for maximum matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091230)