A survey of the algorithmic aspects of modular decomposition
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cites work
- A characterization of perfect graphs
- A Combinatorial Decomposition Theory
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- A Fully dynamic algorithm for recognizing and representing proper interval graphs
- A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
- A linear algorithm to decompose inheritance graphs into modules
- A Linear Recognition Algorithm for Cographs
- A More Effective Linear Kernelization for Cluster Editing
- A more efficient algorithm for perfect sorting by reversals
- A Representation Theorem for Union-Difference Families and Application
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- A simple linear time algorithm for cograph recognition
- A Simple Linear Time LexBFS Cograph Recognition Algorithm
- A simple linear time LexBFS cograph recognition algorithm.
- A tree representation for \(P_ 4\)-sparse graphs
- Algorithm Theory - SWAT 2004
- Algorithmic aspects of a general modular decomposition theory
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms and Computation
- Algorithms – ESA 2005
- An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- Applying modular decomposition to parameterized cluster editing problems
- Complement reducible graphs
- Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs
- Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
- Decomposition of Directed Graphs
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Efficient and practical algorithms for sequential modular decomposition
- Efficient graph representations
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Efficient Parameterized Preprocessing for Cluster Editing
- Fast algorithms to enumerate all common intervals of two permutations
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
- Fully dynamic recognition algorithm and certificate for directed cographs
- Fully dynamic representations of interval graphs
- Graph Classes: A Survey
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Graphs indecomposable with respect to the X-join
- Graphs with unique maximal clumpings
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 1003286 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3906240 (Why is no real title available?)
- scientific article; zbMATH DE number 3460178 (Why is no real title available?)
- scientific article; zbMATH DE number 3580570 (Why is no real title available?)
- scientific article; zbMATH DE number 1741000 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 2038757 (Why is no real title available?)
- scientific article; zbMATH DE number 1478125 (Why is no real title available?)
- scientific article; zbMATH DE number 1508917 (Why is no real title available?)
- scientific article; zbMATH DE number 2086399 (Why is no real title available?)
- scientific article; zbMATH DE number 1456953 (Why is no real title available?)
- scientific article; zbMATH DE number 3414349 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Improved Algorithms for Bicluster Editing
- Incremental modular decomposition
- Kernels for feedback arc set in tournaments
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Longest Common Separable Pattern Among Permutations
- Minimal indecomposable graphs
- Minimal proper interval completions
- Modular decomposition and transitive orientation
- On the X-join decomposition for undirected graphs
- P-Components and the Homogeneous Decomposition of Graphs
- Partition refinement techniques: an interesting algorithmic tool kit
- Partitive hypergraphs
- Polynomial kernels for 3-leaf power graph modification problems
- Practical and efficient circle graph recognition
- Practical and efficient split decomposition via graph-labelled trees
- Primitivity is hereditary for 2-structures
- Recognizing P₄ -Sparse Graphs in Linear Time
- Restricted permutations and the wreath product
- Simple permutations and pattern restricted permutations
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- The longest common pattern problem for two permutations
- Three Partition Refinement Algorithms
- Transitiv orientierbare Graphen
Cited in
(only showing first 100 items - show all)- Algorithmic aspects of a general modular decomposition theory
- The facets of the polytope of modules of a graph.
- Parameterized complexity of the list coloring reconfiguration problem with graph parameters
- Towards an isomorphism dichotomy for hereditary graph classes
- An efficient exact algorithm for triangle listing in large graphs
- The minimum weakly connected independent set problem: polyhedral results and branch-and-cut
- Parameterized algorithms for conflict-free colorings of graphs
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- From modular decomposition trees to rooted median graphs
- 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₄-tidy graphs and tree-cographs
- Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs
- Graph reconstruction in the congested clique
- Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
- Edge deletion problems: branching facilitated by modular decomposition
- Modular decomposition of graphs and the distance preserving property
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- A characterisation of clique-width through nested partitions
- Counting spanning trees using modular decomposition
- Recognition of prime graphs from a prime subgraph
- Parameterized algorithms for edge biclique and related problems
- 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
- Complete edge-colored permutation graphs
- On computing the Gromov hyperbolicity
- Metric dimension of bounded width graphs
- Positional dominance: concepts and algorithms
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Capturing polynomial time using modular decomposition
- 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
- A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
- Polynomial kernels for proper interval completion and related problems
- (Nearly-)tight bounds on the contiguity and linearity of cographs
- Tree-representation of set families and applications to combinatorial decompositions
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Polynomial-time recognition of clique-width 3 graphs
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- Modular-width: an auxiliary parameter for parameterized parallel complexity
- Practical and efficient split decomposition via graph-labelled trees
- Computing \(H\)-joins with application to 2-modular decomposition
- scientific article; zbMATH DE number 1456953 (Why is no real title available?)
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Counting weighted independent sets beyond the permanent
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- Coherent interaction graphs
- Parameterized complexity of geodetic set
- Hierarchical and modularly-minimal vertex colorings
- An Analytic Propositional Proof System on Graphs
- The use of a pruned modular decomposition for maximum matching algorithms on some graph classes
- Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
- Cograph editing: Merging modules is equivalent to editing P₄s
- Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- Some remarks on the order supergraph of the power graph of a finite group
- Partition refinement techniques: an interesting algorithmic tool kit
- Metric Dimension of Bounded Tree-length Graphs
- Drawing graphs using modular decomposition
- A distance measure for large graphs based on prime graphs
- Unifying Two Graph Decompositions with Modular Decomposition
- A Theoretical Framework for Instance Complexity of the Resource-Constrained Project Scheduling Problem
- Graph-Theoretic Concepts in Computer Science
- Graph Drawing
- When can graph hyperbolicity be computed in linear time?
- 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
- Parameterized Complexity of Geodetic Set
- Efficient parallel modular decomposition (extended abstract)
- Modular decomposition of hypergraphs
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- 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
- Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
- Linear time algorithms for NP-hard problems restricted to \textsc{GaTEx} graphs
- Polynomial Turing compressions for some graph problems parameterized by modular-width
- Cutting a tree with subgraph complementation is hard, except for some small trees
- Hypergraphs with polynomial representation: introducing \(r\)-splits
- An exact algorithm for the minimum sum coloring problem on partially decomposable graphs
- Computing and certifying twin-width using logic
- Polynomial Turing compressions for some graph problems parameterized by modular-width
- A canonical tree decomposition for chirotopes
- A canonical tree decomposition for order types, and some applications
- Tree-layout based graph classes: proper chordal graphs
- Complexity and parameterized algorithms for cograph editing
- PACE solver description: hydra prime
- Channel allocation revisited through 1-extendability of graphs
- Conformality of minimal transversals of maximal cliques
- Subprime and superprime graphs
- Preprocessing complexity for some graph problems parameterized by structural parameters
- On P₅-free locally split graphs
- A polynomial bound on the number of minimal separators and potential maximal cliques in P₆-free graphs of bounded clique number
- Zero-sum partitions of abelian groups and their applications to magic- and antimagic-type labelings
- Solving NP-hard problems on \textsc{GaTEx} graphs: linear-time algorithms for perfect orderings, cliques, colorings, and independent sets
- Sequent systems on undirected graphs
This page was built for publication: A survey of the algorithmic aspects of modular decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458504)
