The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes

DOI10.1016/J.DAM.2020.12.018MaRDI QIDQ2659073zbMATH OpenOpenAlexFDO

Authors Guillaume Ducoffe, Alexandru Popa

Publication date 25 March 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

modular decompositionmaximum matchingone-vertex extensionsFPT in P\( P_4\)-structurepruned graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx)

Recommendations

• The use of a pruned modular decomposition for maximum matching algorithms on some graph classes
• A general algorithmic scheme for modular decompositions of hypergraphs and applications
• The parameterised complexity of computing the maximum modularity of a graph
• scientific article; zbMATH DE number 7378595
• A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs
• An Algorithm for the Modular Decomposition of Hypergraphs
• scientific article; zbMATH DE number 177842
• On a graph theoretic division algorithm and maximal decompositions of graphs
• An efficient parallel algorithm for maximum matching for some classes of graphs
• On maximal decompositions of graphs

Cites work

• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 3887731 (Why is no real title available?)
• scientific article; zbMATH DE number 1262810 (Why is no real title available?)
• scientific article; zbMATH DE number 1107732 (Why is no real title available?)
• scientific article; zbMATH DE number 1500541 (Why is no real title available?)
• scientific article; zbMATH DE number 863471 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• scientific article; zbMATH DE number 7561360 (Why is no real title available?)
• scientific article; zbMATH DE number 5279372 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• A semi-strong perfect graph theorem
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• A survey of the algorithmic aspects of modular decomposition
• Algorithm Theory - SWAT 2004
• 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 on cographs
• An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
• Bipartite graphs totally decomposable by canonical decomposition
• Clique-width of graphs defined by one-vertex extensions
• Computing maximum stable sets for distance-hereditary graphs
• Distance-hereditary graphs
• Efficient and practical algorithms for sequential modular decomposition
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding a maximum matching in a circular-arc graph
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Graph theory
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Maximum matching in a convex bipartite graph
• Maximum matching in graphs with an excluded minor
• Maximum matching in regular and almost regular graphs
• Model counting for CNF formulas of bounded modular treewidth
• Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
• Parameterized Algorithms for Modular-Width
• Paths, Trees, and Flowers
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• TWO THEOREMS IN GRAPH THEORY
• Transitiv orientierbare Graphen
• Tree- and forest-perfect graphs

Cited in

(4)

• The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
• From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
• Getting linear time in graphs of bounded neighborhood diversity
• Maximum matching in almost linear time on graphs of bounded clique-width

This page was built for publication: The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes

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