The behavior of clique-width under graph operations and graph transformations
From MaRDI portal
Abstract: Clique-width is a well-known graph parameter. Many NP-hard graph problems admit polynomial-time solutions when restricted to graphs of bounded clique-width. The same holds for NLC-width. In this paper we study the behavior of clique-width and NLC-width under various graph operations and graph transformations. We give upper and lower bounds for the clique-width and NLC-width of the modified graphs in terms of the clique-width and NLC-width of the involved graphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 1696534 (Why is no real title available?)
- scientific article; zbMATH DE number 3906520 (Why is no real title available?)
- scientific article; zbMATH DE number 3745240 (Why is no real title available?)
- scientific article; zbMATH DE number 3482386 (Why is no real title available?)
- scientific article; zbMATH DE number 1979486 (Why is no real title available?)
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- scientific article; zbMATH DE number 1472167 (Why is no real title available?)
- scientific article; zbMATH DE number 1550912 (Why is no real title available?)
- scientific article; zbMATH DE number 821271 (Why is no real title available?)
- scientific article; zbMATH DE number 3290993 (Why is no real title available?)
- A Linear Recognition Algorithm for Cographs
- A characterisation of clique-width through nested partitions
- A partial k-arboretum of graphs with bounded treewidth
- Algorithms for generalized vertex-rankings of partial k-trees
- Approximating clique-width and branch-width
- Automata for the verification of monadic second-order graph properties
- Chordal bipartite graphs of bounded tree- and clique-width
- Circle graph obstructions
- Clique-width and edge contraction
- Clique-width is NP-complete
- Constrained-path labellings on graphs of bounded clique-width
- Deciding Clique-Width for Graphs of Bounded Tree-Width
- Directed NLC-width
- Dynamic algorithms for graphs of bounded treewidth
- Edge dominating set and colorings on graphs with fixed clique-width
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
- Graph Classes: A Survey
- Graph minors. II. Algorithmic aspects of tree-width
- Graph structure and monadic second-order logic. A language-theoretic approach
- Graph theory with applications
- Graph-Theoretic Concepts in Computer Science
- Handle-rewriting hypergraph grammars
- Line graphs of bounded clique-width
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Linear time solvable optimization problems on graphs of bounded clique-width
- Multicut on graphs of bounded clique-width
- NLC-2 Graph Recognition and Isomorphism
- NLC\(_{2}\)-decomposition in polynomial time
- New graph classes of bounded clique-width
- On deciding switching equivalence of graphs
- On powers of graphs of bounded NLC-width (clique-width)
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- On the Relationship Between Clique-Width and Treewidth
- On the clique-width of some perfect graph classes
- On the corona of two graphs
- On the relationship between NLC-width and linear NLC-width
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- Rank-width and vertex-minors
- Recent developments on graphs of bounded clique-width
- Recognizing \(P_ 3\)-structure: A switching approach
- S-functions for graphs
- Seidel minor, permutation graphs and combinatorial properties
- The bandwidth problem and operations on graphs
- The bi-join decomposition
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Upper bounds to the clique width of graphs
- Vertex disjoint paths on clique-width bounded graphs
- \(k\)-NLC graphs and polynomial algorithms
Cited in
(20)- Induced betweenness in order-theoretic trees
- On a disparity between relative cliquewidth and relative NLC-width
- Stability, vertex stability, and unfrozenness for special graph classes
- Parameterized complexity of graph burning
- Clique‐width: Harnessing the power of atoms
- Parameterized Complexity of Graph Burning
- On switching classes, NLC-width, cliquewidth and treewidth
- \(b\)-coloring parameterized by clique-width
- Colouring diamond-free graphs
- Bounding the mim‐width of hereditary graph classes
- Clique-width for graph classes closed under complementation
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Grammars and clique-width bounds from split decompositions
- On quasi-planar graphs: clique-width and logical description
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Bounding the Mim-Width of Hereditary Graph Classes.
- Bounds on the Twin-Width of Product Graphs
- scientific article; zbMATH DE number 7204407 (Why is no real title available?)
- List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
- Revising Johnson's table for the 21st century
This page was built for publication: The behavior of clique-width under graph operations and graph transformations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q519907)
