Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Linear Rank-Width and Linear Clique-Width of Trees
verfasst von : Isolde Adler, Mamadou Moustapha Kanté
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
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
We show that for every forest
T
the linear rank-width of
T
is equal to the path-width of
T
, and we show that the linear clique-width of
T
equals the path-width of
T
plus two, provided that
T
contains a path of length three. It follows that both linear rank-width and linear clique-width of forests can be computed in linear time. Using our characterization of linear rank-width of forests, we determine the set of minimal excluded acyclic vertex-minors for the class of graphs of linear rank-width at most
k
.