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 (73)

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

This page was built for publication: Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations