Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width
From MaRDI portal
Publication:3007630
DOI10.1007/978-3-642-20712-9_18zbMath1332.68078OpenAlexW77305285MaRDI QIDQ3007630
Pinar Heggernes, Daniel Meister, Udi Rotics
Publication date: 17 June 2011
Published in: Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_18
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (5)
Clique-width of path powers ⋮ A SAT Approach to Clique-Width ⋮ Graph classes with and without powers of bounded clique-width ⋮ Clique-width with an inactive label ⋮ A characterisation of clique-width through nested partitions
Cites Work
- Unnamed Item
- Unnamed Item
- New graph classes of bounded clique-width
- Recent developments on graphs of bounded clique-width
- On a disparity between relative cliquewidth and relative NLC-width
- Chordal bipartite graphs of bounded tree- and clique-width
- 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
- Linear layouts measuring neighbourhoods in graphs
- The relative clique-width of a graph
- Clique-Width is NP-Complete
- From Tree-Width to Clique-Width: Excluding a Unit Interval Graph
- A Complete Characterisation of the Linear Clique-Width of Path Powers
- Deciding Clique-Width for Graphs of Bounded Tree-Width
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- On the Relationship Between Clique-Width and Treewidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width
