The behavior of clique-width under graph operations and graph transformations
From MaRDI portal
Publication:519907
DOI10.1007/S00224-016-9685-1zbMATH Open1358.05239arXivcs/0701185OpenAlexW1785928421MaRDI QIDQ519907FDOQ519907
Authors: Frank Gurski 
Publication date: 31 March 2017
Published in: Theory of Computing Systems (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/cs/0701185
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Graph Classes: A Survey
- A partial k-arboretum of graphs with bounded treewidth
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- A characterisation of clique-width through nested partitions
- Handle-rewriting hypergraph grammars
- Approximating clique-width and branch-width
- On the corona of two graphs
- Graph structure and monadic second-order logic. A language-theoretic approach
- Graph theory with applications
- Clique-width is NP-complete
- Deciding Clique-Width for Graphs of Bounded Tree-Width
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the clique-width of some perfect graph classes
- On the Relationship Between Clique-Width and Treewidth
- Title not available (Why is that?)
- Recent developments on graphs of bounded clique-width
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Automata for the verification of monadic second-order graph properties
- Graph minors. II. Algorithmic aspects of tree-width
- Circle graph obstructions
- Rank-width and vertex-minors
- A Linear Recognition Algorithm for Cographs
- Title not available (Why is that?)
- Title not available (Why is that?)
- New graph classes of bounded clique-width
- S-functions for graphs
- Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
- The bi-join decomposition
- Dynamic algorithms for graphs of bounded treewidth
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- \(k\)-NLC graphs and polynomial algorithms
- NLC-2 Graph Recognition and Isomorphism
- Edge dominating set and colorings on graphs with fixed clique-width
- Line graphs of bounded clique-width
- On the relationship between NLC-width and linear NLC-width
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- NLC\(_{2}\)-decomposition in polynomial time
- Chordal bipartite graphs of bounded tree- and clique-width
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Vertex disjoint paths on clique-width bounded graphs
- Seidel minor, permutation graphs and combinatorial properties
- The bandwidth problem and operations on graphs
- On deciding switching equivalence of graphs
- Algorithms for generalized vertex-rankings of partial k-trees
- Recognizing \(P_ 3\)-structure: A switching approach
- Constrained-path labellings on graphs of bounded clique-width
- Clique-width and edge contraction
- On powers of graphs of bounded NLC-width (clique-width)
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Title not available (Why is that?)
- Multicut on graphs of bounded clique-width
- Directed NLC-width
Cited In (20)
- Bounding the Mim-Width of Hereditary Graph Classes.
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Stability, vertex stability, and unfrozenness for special graph classes
- On switching classes, NLC-width, cliquewidth and treewidth
- Title not available (Why is that?)
- On a disparity between relative cliquewidth and relative NLC-width
- List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
- Colouring diamond-free graphs
- Clique‐width: Harnessing the power of atoms
- \(b\)-coloring parameterized by clique-width
- Parameterized Complexity of Graph Burning
- Parameterized complexity of graph burning
- 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
- Bounding the mim‐width of hereditary graph classes
- Induced betweenness in order-theoretic trees
- Revising Johnson's table for the 21st century
- Bounds on the Twin-Width of Product Graphs
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)
