Thread Graphs, Linear Rank-Width and Their Algorithmic Applications

DOI10.1007/978-3-642-19222-7_5zbMath1295.68172OpenAlexW2108354262MaRDI QIDQ3000492

Robert Ganian

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (19)

Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Graphs of bounded depth‐2 rank‐brittleness ⋮ Obstructions for linear rank-width at most 1 ⋮ Graphs of small rank-width are pivot-minors of graphs of small tree-width ⋮ Thread Graphs, Linear Rank-Width and Their Algorithmic Applications ⋮ Neighbourhood-width of trees ⋮ Several notions of rank-width for countable graphs ⋮ Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm ⋮ Vertex-minors of graphs: a survey ⋮ Scattered Classes of Graphs ⋮ Tree pivot-minors and linear rank-width ⋮ Excluded vertex-minors for graphs of linear rank-width at most \(k\) ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Comparing linear width parameters for directed graphs ⋮ Unnamed Item ⋮ Linear rank-width and linear clique-width of trees ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Improved Bandwidth Approximation for Trees and Chordal Graphs
• Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
• Better Polynomial Algorithms on Graphs of Bounded Rank-Width
• Graph minors. II. Algorithmic aspects of tree-width
• The bandwidth problem for graphs and matrices—a survey
• Pathwidth is NP-Hard for Weighted Trees

This page was built for publication: Thread Graphs, Linear Rank-Width and Their Algorithmic Applications