The behavior of clique-width under graph operations and graph transformations
From MaRDI portal
Publication:519907
DOI10.1007/s00224-016-9685-1zbMath1358.05239arXivcs/0701185OpenAlexW1785928421MaRDI QIDQ519907
Publication date: 31 March 2017
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0701185
Graph labelling (graceful graphs, bandwidth, etc.) (05C78) 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)
Related Items (16)
Induced betweenness in order-theoretic trees ⋮ Parameterized complexity of graph burning ⋮ Colouring diamond-free graphs ⋮ Grammars and clique-width bounds from split decompositions ⋮ On quasi-planar graphs: clique-width and logical description ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Parameterized Complexity of Graph Burning ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ Unnamed Item ⋮ Revising Johnson's table for the 21st century
Cites Work
- Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- New graph classes of bounded clique-width
- Directed NLC-width
- Recent developments on graphs of bounded clique-width
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- The bandwidth problem and operations on graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- On deciding switching equivalence of graphs
- S-functions for graphs
- A partial k-arboretum of graphs with bounded treewidth
- Circle graph obstructions
- \(k\)-NLC graphs and polynomial algorithms
- Algorithms for generalized vertex-rankings of partial k-trees
- Dynamic algorithms for graphs of bounded treewidth
- Chordal bipartite graphs of bounded tree- and clique-width
- Edge dominating set and colorings on graphs with fixed clique-width
- Recognizing \(P_ 3\)-structure: A switching approach
- Automata for the verification of monadic second-order graph properties
- Constrained-path labellings on graphs of bounded clique-width
- 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
- Clique-width and edge contraction
- Handle-rewriting hypergraph grammars
- On powers of graphs of bounded NLC-width (clique-width)
- Line graphs of bounded clique-width
- The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
- Approximating clique-width and branch-width
- Vertex disjoint paths on clique-width bounded graphs
- On the corona of two graphs
- Rank-width and vertex-minors
- On the relationship between NLC-width and linear NLC-width
- A SAT Approach to Clique-Width
- Seidel Minor, Permutation Graphs and Combinatorial Properties
- Multicut on Graphs of Bounded Clique-Width
- The bi-join decomposition
- NLC-2 Graph Recognition and Isomorphism
- Clique-Width is NP-Complete
- A Linear Recognition Algorithm for Cographs
- Graph minors. II. Algorithmic aspects of tree-width
- Graph Classes: A Survey
- Deciding Clique-Width for Graphs of Bounded Tree-Width
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- NLC2-DECOMPOSITION IN POLYNOMIAL TIME
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- On the Relationship Between Clique-Width and Treewidth
- Graph-Theoretic Concepts in Computer Science
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The behavior of clique-width under graph operations and graph transformations
