Clique-width of path powers
DOI10.1016/J.DAM.2015.11.009zbMATH Open1333.05221OpenAlexW2286033726MaRDI QIDQ266933FDOQ266933
Authors: Pinar Heggernes, Daniel Meister, Charis Papadopoulos, Udi Rotics 
Publication date: 7 April 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2015.11.009
Recommendations
- A Complete Characterisation of the Linear Clique-Width of Path Powers
- Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
- Graph classes with and without powers of bounded clique-width
- The Clique-Width of Tree-Power and Leaf-Power Graphs
- The NLC-width and clique-width for powers of graphs of bounded tree-width
clique-widthforbidden induced subgraphs characterisationlinear-time computationproper interval graphs
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Paths and cycles (05C38)
Cites Work
- Graph Classes: A Survey
- Complement reducible graphs
- Algorithmic graph theory and perfect graphs
- 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
- Linear layouts measuring neighbourhoods in graphs
- The relative clique-width of a graph
- Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
- Graph structure and monadic second-order logic. A language-theoretic approach
- Clique-width is NP-complete
- A Complete Characterisation of the Linear Clique-Width of Path Powers
- On the clique-width of some perfect graph classes
- Title not available (Why is that?)
- Minimal classes of graphs of unbounded clique-width
- Graphs of linear clique-width at most 3
- On a disparity between relative cliquewidth and relative NLC-width
Cited In (9)
- Mim-width. III. Graph powers and generalized distance domination problems
- The Clique-Width of Tree-Power and Leaf-Power Graphs
- Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
- Clique width of partner limited graphs
- Graph classes with and without powers of bounded clique-width
- Clique-width of point configurations
- Clique-width of full bubble model graphs
- A Complete Characterisation of the Linear Clique-Width of Path Powers
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
This page was built for publication: Clique-width of path powers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266933)
