A survey of the algorithmic aspects of modular decomposition

DOI10.1016/j.cosrev.2010.01.001zbMath1302.68140OpenAlexW2019030165MaRDI QIDQ458504

Publication date: 7 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.193.9193

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (71)

Parameterized Complexity of Geodetic Set ⋮ Hierarchical and modularly-minimal vertex colorings ⋮ Parameterized algorithms for edge biclique and related problems ⋮ An Analytic Propositional Proof System on Graphs ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ Unnamed Item ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Grammars and clique-width bounds from split decompositions ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Neighborhood covering and independence on $P_4$-tidy graphs and tree-cographs ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ Metric Dimension of Bounded Width Graphs ⋮ A SAT Approach to Clique-Width ⋮ A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs ⋮ Complete edge-colored permutation graphs ⋮ Polynomial kernels for proper interval completion and related problems ⋮ (Nearly-)tight bounds on the contiguity and linearity of cographs ⋮ Characterizations, probe and sandwich problems on $( k , \ell )$-cographs ⋮ Graph reconstruction in the congested clique ⋮ Spined categories: generalizing tree-width beyond graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Tree-representation of set families and applications to combinatorial decompositions ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Polynomial-time recognition of clique-width $\leq 3$ graphs ⋮ Symmetric maximal Condorcet domains ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Computing well-covered vector spaces of graphs using modular decomposition ⋮ Modules in Robinson Spaces ⋮ $\boldsymbol{(\alpha, \beta )}$-Modules in Graphs ⋮ On the (non-)existence of polynomial kernels for $P _{l }$-free edge modification problems ⋮ Positional Dominance: Concepts and Algorithms ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Counting spanning trees using modular decomposition ⋮ Unnamed Item ⋮ Recognition of prime graphs from a prime subgraph ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Covering minimal separators and potential maximal cliques in $P_t$-free graphs ⋮ Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity ⋮ Computing $H$-joins with application to 2-modular decomposition ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ An efficient exact algorithm for triangle listing in large graphs ⋮ Approximate association via dissociation ⋮ The minimum weakly connected independent set problem: polyhedral results and branch-and-cut ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Complexity and parameterized algorithms for cograph editing ⋮ A distance measure for large graphs based on prime graphs ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ Unnamed Item ⋮ On the complete width and edge clique cover problems ⋮ On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Parameterized algorithms for conflict-free colorings of graphs ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Modular decomposition of graphs and the distance preserving property ⋮ On Computing the Gromov Hyperbolicity ⋮ From modular decomposition trees to rooted median graphs ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ Counting Weighted Independent Sets beyond the Permanent ⋮ Polynomial-time algorithms for minimum weighted colorings of $(P_5, \overline{P}_5)$-free graphs and similar graph classes ⋮ Parameterized Complexity of Geodetic Set ⋮ A characterisation of clique-width through nested partitions ⋮ A Theoretical Framework for Instance Complexity of the Resource-Constrained Project Scheduling Problem ⋮ Metric Dimension of Bounded Tree-length Graphs

Cites Work

This page was built for publication: A survey of the algorithmic aspects of modular decomposition