Carregant...
Carregant...

Vés al contingut (premeu Retorn)

1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor

Autor
Demaine, E.; Hajiaghayi, M.; Thilikos, D.
Tipus d'activitat
Document cientificotècnic
Data
2002-05
Codi
LSI-02-40-R
Repositori
http://hdl.handle.net/2117/97497 Obrir en finestra nova
Resum
We give polynomial-time constant-factor approximation algorithms for the treewidth and branchwidth of any H-minor-free graph for a given graph H with crossing number at most 1. The approximation factors are 1.5 for treewidth and 2.25 for branchwidth. In particular, our result directly applies to classes of nonplanar graphs such as K_{5}-minor-free graphs and K_{3,3}-minor-free graphs. Along the way, we present a polynomial-time algorithm to decompose H-minor-free graphs into planar graphs and gr...
Citació
Demaine, E., Hajiaghayi, M., Thilikos, D. "1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor". 2002.
Paraules clau
Polynomial-time constant-factor approximation algorithms, Treewidth of graphs
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

  • Demaine, Erik D.  (autor)
  • Hajiaghayi, Mohammad Taghi  (autor)
  • Thilikos Touloupas, Dimitrios  (autor)

Arxius