Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations

DOI10.1007/978-3-540-70575-8_52zbMath1153.68410WikidataQ57535775 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

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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