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

DOI10.1016/j.dam.2020.12.018OpenAlexW3115625065MaRDI QIDQ2659073

Alexandru Popa, Guillaume Ducoffe

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

maximum matchingmodular decompositionone-vertex extensionsFPT in P\( P_4\)-structurepruned graphs

Mathematics Subject Classification ID

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

Related Items (2)

From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Maximum matching in almost linear time on graphs of bounded clique-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
• Model counting for CNF formulas of bounded modular treewidth
• A survey of the algorithmic aspects of modular decomposition
• An O(\(n\)) time algorithm for maximum matching on cographs
• Clique-width of graphs defined by one-vertex extensions
• Distance-hereditary graphs
• A semi-strong perfect graph theorem
• Finding a maximum matching in a circular-arc graph
• Tree- and forest-perfect graphs
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
• Maximum matching in regular and almost regular graphs
• Computing maximum stable sets for distance-hereditary graphs
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• Parameterized Algorithms for Modular-Width
• TWO THEOREMS IN GRAPH THEORY
• Fast Algorithms for Finding Nearest Common Ancestors
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• A Linear Recognition Algorithm for Cographs
• A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
• Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
• Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
• BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION
• Algorithm Theory - SWAT 2004
• Paths, Trees, and Flowers
• Transitiv orientierbare Graphen
• Maximum matching in a convex bipartite graph
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs

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