Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Linear Rank-Width of Distance-Hereditary Graphs
verfasst von : Isolde Adler, Mamadou Moustapha Kanté, O-joung Kwon
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We present a characterization of the linear rank-width of distance-hereditary graphs. Using the characterization, we show that the linear rank-width of every \(n\)-vertex distance-hereditary graph can be computed in time \(\mathcal {O}(n^2\cdot \log (n))\), and a linear layout witnessing the linear rank-width can be computed with the same time complexity. For our characterization, we combine modifications of canonical split decompositions with an idea of [Megiddo, Hakimi, Garey, Johnson, Papadimitriou: The complexity of searching a graph. JACM 1988], used for computing the path-width of trees. We also provide a set of distance-hereditary graphs which contains the set of distance-hereditary vertex-minor obstructions for linear rank-width. The set given in [Jeong, Kwon, Oum: Excluded vertex-minors for graphs of linear rank-width at most k. STACS 2013: 221–232] is a subset of our obstruction set.