A new linear algorithm for modular decomposition
From MaRDI portal
Recommendations
- Algorithm Theory - SWAT 2004
- Efficient and practical algorithms for sequential modular decomposition
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- A survey of the algorithmic aspects of modular decomposition
- Algorithmic aspects of a general modular decomposition theory
Cited in
(only showing first 100 items - show all)- Structure and stability number of chair-, co-P- and gem-free graphs revisited
- Algorithmic aspects of a general modular decomposition theory
- Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
- Probe threshold and probe trivially perfect graphs
- \(P_ 4\)-trees and substitution decomposition
- Modular decomposition and transitive orientation
- Complexity of list coloring problems with a fixed total number of colors
- \(P_{4}\)-laden graphs: A new class of brittle graphs
- Bi-complement reducible graphs
- On semi-\(P_ 4\)-sparse graphs
- Scattering number and modular decomposition
- A nice class for the vertex packing problem
- The monadic second-order logic of graphs. X: Linear orderings
- On the closure of graphs under substitution
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- Minimal indecomposable graphs
- On extended P₄-reducible and extended P₄-sparse graphs
- A monadic second-order definition of the structure of convex hypergraphs.
- On variations of \(P_{4}\)-sparse graphs
- Stability number of bull- and chair-free graphs revisited
- The facets of the polytope of modules of a graph.
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- On stable cutsets in graphs
- A note on transitive orientations with maximum sets of sources and sinks
- The \(\{-2,-1\}\)-selfdual and decomposable tournaments
- Total dominating sequences in trees, split graphs, and under modular decomposition
- An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\)
- On the structure of (\(P_{5}\),\,gem)-free graphs
- A simple linear time algorithm for cograph recognition
- Linear-time modular decomposition of directed graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Bipartite-perfect graphs
- Recognition of some perfectly orderable graph classes
- The clique operator on cographs and serial graphs
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
- A linear algorithm to decompose inheritance graphs into modules
- An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
- The multiple domination and limited packing problems in graphs
- Recognition and isomorphism of tree-like \(P_4\)-connected graphs
- Upper bounds to the clique width of graphs
- Hitting subgraphs in \(P_4\)-tidy graphs
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- Neighborhood covering and independence on P₄-tidy graphs and tree-cographs
- On the Carathéodory and exchange numbers of geodetic convexity in graphs
- Generalized limited packings of some graphs with a limited number of \(P_4\)-partners
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- The complexity of modular decomposition of Boolean functions
- Counting spanning trees using modular decomposition
- The clique operator on graphs with few \(P_{4}\)'s
- The recognizability of sets of graphs is a robust property
- The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
- Linear-time algorithms for maximum sets of sources and sinks
- Efficient and practical algorithms for sequential modular decomposition
- Recognizing k-equistable graphs in FPT time
- An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
- Computing role assignments of split graphs
- Linear time split decomposition revisited
- The bi-join decomposition
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms
- Incremental modular decomposition
- 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
- scientific article; zbMATH DE number 1741000 (Why is no real title available?)
- A fully dynamic algorithm for the recognition of P₄-sparse graphs
- A survey of the algorithmic aspects of modular decomposition
- The definition in monadic second-order logic of modular decompositions of ordered graphs
- scientific article; zbMATH DE number 6963897 (Why is no real title available?)
- Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
- Prime Testing for the Split Decomposition of a Graph
- Solving the weighted k-separator problem in graphs with specific modules
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- Two complexity results for the vertex coloring problem
- Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions
- Cograph editing: Merging modules is equivalent to editing P₄s
- Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
- Drawing graphs using modular decomposition
- A distance measure for large graphs based on prime graphs
- Algorithm Theory - SWAT 2004
- Graph Drawing
- On minimal forbidden subgraph characterizations of balanced graphs
- Nesting of prime substructures in k-ary relations
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Efficient parallel modular decomposition (extended abstract)
- Modular decomposition of hypergraphs
- Computing the hull and interval numbers in the weakly toll convexity
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
- On new algorithmic techniques for the weighted vertex coloring problem
- A new characterization of P₄-connected graphs
- Polynomial cases for the vertex coloring problem
- Enumerating minimal defensive alliances
- Grundy double domination number: bounds, graph operations, and efficient computation for P₄-tidy graphs
- Computing and certifying twin-width using logic
- A new algorithm for decomposition of graphical models
- Subprime and superprime graphs
- Prime and critical digraphs
This page was built for publication: A new linear algorithm for modular decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4954442)
