Polynomial-time recognition of clique-width \(\leq 3\) graphs

DOI10.1016/J.DAM.2011.03.020zbMath1237.05147OpenAlexW2067475075MaRDI QIDQ415285

Jean-Marc Lanlignel, Michel A. Habib, Udi Rotics, Derek Gordon Corneil, Bruce A. Reed

Publication date: 11 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.03.020

zbMATH Keywords

polynomial-time algorithmclique-width computation

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (19)

Rank-width: algorithmic and structural results ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ A SAT Approach to Clique-Width ⋮ Graph classes with and without powers of bounded clique-width ⋮ Bounding clique-width via perfect graphs ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Locating Eigenvalues of Symmetric Matrices - A Survey ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Clique-width with an inactive label ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Computing the clique-width of cactus graphs ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Alliances in graphs of bounded clique-width ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Unnamed Item ⋮ Digraphs of Bounded Width ⋮ Clique-width and edge contraction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• New graph classes of bounded clique-width
• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• Modular decomposition and transitive orientation
• \(k\)-NLC graphs and polynomial algorithms
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• Edge dominating set and colorings on graphs with fixed clique-width
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Line graphs of bounded clique-width
• Approximating clique-width and branch-width
• NLC-2 Graph Recognition and Isomorphism
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Clique-Width is NP-Complete
• A Fast Algorithm for the Decomposition of Graphs and Posets
• Transforming trees by successive local complementations
• Decomposition of Directed Graphs
• An O(n2) Algorithm for Undirected Split Decomposition
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Approximating rank-width and clique-width quickly
• PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
• NLC₂-DECOMPOSITION IN POLYNOMIAL TIME
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH

This page was built for publication: Polynomial-time recognition of clique-width \(\leq 3\) graphs