Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations

DOI10.1007/978-3-540-70575-8_52zbMath1153.68410OpenAlexW1562378785WikidataQ57535775 ScholiaQ57535775MaRDI QIDQ3521955

Marc Tedder, Christophe Paul, Derek Gordon Corneil, Michel A. Habib

Publication date: 28 August 2008

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70575-8_52

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Iterated Type Partitions, Parameterized complexity of locally minimal defensive alliances, The balanced satisfactory partition problem, Recognizing well covered graphs of families with special \(P _{4}\)-components, Target Set Selection in Dense Graph Classes, On the harmless set problem parameterized by treewidth, Unnamed Item, Unnamed Item, Parameterized algorithms for the module motif problem, Graph searches and their end vertices, The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes, 4-coloring \((P_6, \text{bull})\)-free graphs, From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, Polynomial kernels for 3-leaf power graph modification problems, Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs, Erdös-Pósa Property of Obstructions to Interval Graphs, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Metric Dimension of Bounded Width Graphs, Grundy Distinguishes Treewidth from Pathwidth, A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs, On the parameterized complexity of the acyclic matching problem, Parameterizing path partitions, Triangle‐free equimatchable graphs, Efficient parameterized algorithms for computing all-pairs shortest paths, Computing densest \(k\)-subgraph with structural parameters, Erdős–Pósa property of obstructions to interval graphs, Computing and listing avoidable vertices and paths, Tree-representation of set families and applications to combinatorial decompositions, Parameterized complexity for iterated type partitions and modular-width, Polynomial-time recognition of clique-width \(\leq 3\) graphs, Computing and listing avoidable vertices and paths, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, Computing well-covered vector spaces of graphs using modular decomposition, Parameterized Complexity of Safe Set, Cograph editing: Merging modules is equivalent to editing P_4s, A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs, Counting spanning trees using modular decomposition, Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number, Unnamed Item, A survey of the algorithmic aspects of modular decomposition, How Bad is the Freedom to Flood-It?, Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes, Polynomial cases for the vertex coloring problem, Restricted coloring problems on graphs with few \(P_4\)'s, The Small Set Vertex expansion problem, Efficient and Adaptive Parameterized Algorithms on Modular Decompositions, Refined notions of parameterized enumeration kernels with applications to matching cut enumeration, Solving some NP-complete problems using split decomposition, Polynomial-time algorithm for isomorphism of graphs with clique-width at most three, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques, Transitive orientations in bull-reducible Berge graphs, On the Grundy number of graphs with few \(P_4\)'s, Minimal separators in extended \(P_4\)-laden graphs, Parameterized algorithms for the happy set problem, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On the complete width and edge clique cover problems, Cluster Editing: Kernelization Based on Edge Cuts, Partitioning graphs into induced subgraphs, The \(k\)-distinct language: parameterized automata constructions, Parameterized complexity of satisfactory partition problem, Graph square roots of small distance from degree one graphs, Minimum eccentricity shortest path problem with respect to structural parameters, Independent set reconfiguration parameterized by modular-width, Subgraph isomorphism on graph classes that exclude a substructure, Minimum eccentricity shortest path problem with respect to structural parameters, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Recognizing k-equistable Graphs in FPT Time, Counting Weighted Independent Sets beyond the Permanent, Unifying the representation of symmetric crossing families and weakly partitive families, Metric Dimension of Bounded Tree-length Graphs