skip to main content

A 3-approximation for the pathwidth of Halin graphs

Fomin, Fedor V. ; Thilikos, Dimitrios M.

Journal of Discrete Algorithms, 2006, Vol.4(4), pp.499-510 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    A 3-approximation for the pathwidth of Halin graphs
  • Autor: Fomin, Fedor V. ; Thilikos, Dimitrios M.
  • Assuntos: Halin Graph ; Pathwidth ; Linear Width
  • É parte de: Journal of Discrete Algorithms, 2006, Vol.4(4), pp.499-510
  • Descrição: We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.