Polynomial-time recognition of clique-width 3 graphs
DOI10.1016/J.DAM.2011.03.020zbMATH Open1237.05147OpenAlexW2067475075MaRDI QIDQ415285FDOQ415285
Jean-Marc Lanlignel, Michel Habib, Derek G. Corneil, Udi Rotics, Bruce 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
Recommendations
- Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
- Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
- Linear time solvable optimization problems on graphs of bounded clique-width
- Graphs of linear clique-width at most 3
- Recent developments on graphs of bounded clique-width
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Modular decomposition and transitive orientation
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Handle-rewriting hypergraph grammars
- Approximating clique-width and branch-width
- Clique-Width is NP-Complete
- Title not available (Why is that?)
- Deciding Clique-Width for Graphs of Bounded Tree-Width
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- On the Relationship Between Clique-Width and Treewidth
- Title not available (Why is that?)
- Decomposition of Directed Graphs
- New graph classes of bounded clique-width
- A survey of the algorithmic aspects of modular decomposition
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- \(k\)-NLC graphs and polynomial algorithms
- NLC-2 Graph Recognition and Isomorphism
- Edge dominating set and colorings on graphs with fixed clique-width
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Line graphs of bounded clique-width
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
- An O(n2) Algorithm for Undirected Split Decomposition
- Structure and stability number of chair-, co-P- and gem-free graphs revisited
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
- A Fast Algorithm for the Decomposition of Graphs and Posets
- Transforming trees by successive local complementations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- Title not available (Why is that?)
- Approximating rank-width and clique-width quickly
- PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
- NLC2-DECOMPOSITION IN POLYNOMIAL TIME
- Title not available (Why is that?)
Cited In (23)
- Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Bounding the Clique-Width of H-free Chordal Graphs
- Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
- Digraphs of Bounded Width
- Clique-Width for Graph Classes Closed under Complementation
- Title not available (Why is that?)
- Computing the clique-width of cactus graphs
- Title not available (Why is that?)
- Clique-width and edge contraction
- Alliances in graphs of bounded clique-width
- Title not available (Why is that?)
- Bounding the clique-width of \(H\)-free split graphs
- Bounding clique-width via perfect graphs
- A SAT Approach to Clique-Width
- Clique-width with an inactive label
- Practical and efficient split decomposition via graph-labelled trees
- Graph classes with and without powers of bounded clique-width
- Locating Eigenvalues of Symmetric Matrices - A Survey
- Bounding the clique-width of \(H\)-free split graphs
- The relative clique-width of a graph
- Rank-width: algorithmic and structural results
- The behavior of clique-width under graph operations and graph transformations
This page was built for publication: Polynomial-time recognition of clique-width \(\leq 3\) graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q415285)
