Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm

DOI10.1007/S00453-016-0164-5zbMath1361.05036arXiv1403.1081OpenAlexW2963991780WikidataQ59889091 ScholiaQ59889091MaRDI QIDQ527431

O-joung Kwon, Mamadou Moustapha Kanté, Isolde Adler

Publication date: 11 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.1081

zbMATH Keywords

distance-hereditary graphslinear rank-widthrank-widthmatroid branch-widthmatroid path-widthvertex-minors

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Combinatorial aspects of matroids and geometric lattices (05B35) Graph minors (05C83) Distance in graphs (05C12)

Related Items (7)

Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Graphs of bounded depth‐2 rank‐brittleness ⋮ Twin-distance-hereditary digraphs ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Well-quasi-ordering of matrices under Schur complement and applications to directed graphs
• Excluded vertex-minors for graphs of linear rank-width at most \(k\)
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Distance-hereditary graphs
• The vertex separation and search number of a graph
• Distance labeling scheme and split decomposition
• Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions
• Branch-width and well-quasi-ordering in matroids and graphs.
• Upper bounds to the clique width of graphs
• Linear rank-width and linear clique-width of trees
• Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
• The rank-width of edge-coloured graphs
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Solving Rota's Conjecture
• Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
• Matroid Pathwidth and Code Trellis Complexity
• Circle graph obstructions under pivoting
• The complexity of searching a graph
• Transforming trees by successive local complementations
• A Combinatorial Decomposition Theory
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Constructive algorithm for path-width of matroids
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Lectures on matroids

This page was built for publication: Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm