skip to main content

Linear rank-width and linear clique-width of trees.(Report)

Adler, Isolde ; Kante, Mamadou Moustapha

Theoretical Computer Science, July 19, 2015, Vol.589, p.87(12) [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    Linear rank-width and linear clique-width of trees.(Report)
  • Autor: Adler, Isolde ; Kante, Mamadou Moustapha
  • É parte de: Theoretical Computer Science, July 19, 2015, Vol.589, p.87(12)
  • Descrição: To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.tcs.2015.04.021 Byline: Isolde Adler, Mamadou Moustapha Kante Abstract: We show that for every forest T the linear rank-width of T is equal to the path-width of T, and 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. Author Affiliation: (a) Institut fur Informatik, Goethe-Universitat, Frankfurt, Germany (b) Clermont-Universite, Universite Blaise Pascal, LIMOS, CNRS, France Article History: Received 5 September 2014; Revised 9 April 2015; Accepted 13 April 2015 Article Note: (footnote) [star] A preliminary version of this paper appeared in [2].
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.