Linear rank-width and linear clique-width of trees

DOI10.1016/j.tcs.2015.04.021zbMath1319.05096OpenAlexW2139665196WikidataQ57950033 ScholiaQ57950033MaRDI QIDQ2346380

Mamadou Moustapha Kanté, Isolde Adler

Publication date: 1 June 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.04.021

zbMATH Keywords

linear clique widthlinear rank widthvertex minors

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Rank-width: algorithmic and structural results ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ Unnamed Item ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ Graphs of bounded depth‐2 rank‐brittleness ⋮ Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Clique-width with an inactive label
• Graphs of linear clique-width at most 3
• Excluded vertex-minors for graphs of linear rank-width at most \(k\)
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Upper bounds on the size of obstructions and intertwines
• Circle graph obstructions
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• The vertex separation and search number of a graph
• Fugitive-search games on graphs and related parameters
• Searching and pebbling
• Upper bounds to the clique width of graphs
• Obstructions for linear rank-width at most 1
• Approximating clique-width and branch-width
• Linear layouts measuring neighbourhoods in graphs
• Rank-width and vertex-minors
• On the relationship between NLC-width and linear NLC-width
• The relative clique-width of a graph
• Linear Rank-Width and Linear Clique-Width of Trees
• Linear Rank-Width of Distance-Hereditary Graphs
• Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
• Pathwidth of Circular-Arc Graphs
• Clique-Width is NP-Complete
• A Complete Characterisation of the Linear Clique-Width of Path Powers
• The complexity of searching a graph
• Transforming trees by successive local complementations
• Treewidth and Pathwidth of Permutation Graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• The pathwidth and treewidth of cographs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Linear rank-width and linear clique-width of trees