To access the full text documents, please follow this link: http://hdl.handle.net/2117/97488
| dc.contributor | Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
|---|---|
| dc.contributor.author | Hajiaghayi, Mohammad Taghi |
| dc.contributor.author | Nishimura, Naomi |
| dc.contributor.author | Ragde, Prabhakar |
| dc.contributor.author | Thilikos Touloupas, Dimitrios |
| dc.date | 2002-05 |
| dc.identifier.citation | Hajiaghayi, M., Nishimura, N., Ragde, P., Thilikos, D. "Fast approximation schemes for K_{3,3}-minor-free or K_{5}-minor-free graphs". 2002. |
| dc.identifier.uri | http://hdl.handle.net/2117/97488 |
| dc.description.abstract | As the class of graphs of bounded treewidth is of limited size, we need to solve NP-hard problems for wider classes of graphs than this class. Eppstein introduced a new concept which can be considered as a generalization of bounded treewidth. A graph G has {em locally bounded treewidth} if for each vertex v of G, the treewidth of the subgraph of G induced on all vertices of distance at most r from v is only a function of r, called local treewidth. So far the only graphs determined to have small local treewidth are planar graphs. In this paper, we prove that any graph excluding one of K_{5} or K_{3,3} as a minor has local treewidth bounded by 3k+4. As a result, we can design practical polynomial-time approximation schemes for both minimization and maximization problems on these classes of non-planar graphs. |
| dc.language.iso | eng |
| dc.relation | LSI-02-44-R |
| dc.rights | info:eu-repo/semantics/openAccess |
| dc.subject | Àrees temàtiques de la UPC::Informàtica |
| dc.subject | Graphs of bounded treewidth |
| dc.subject | Polynomial-time approximation |
| dc.subject | Non-planar graphs |
| dc.title | Fast approximation schemes for K_{3,3}-minor-free or K_{5}-minor-free graphs |
| dc.type | info:eu-repo/semantics/publishedVersion |
| dc.type | info:eu-repo/semantics/report |
Related documents
Other documents of the same author
Nishimura, Naomi; Ragde, Prabhakar; Thilikos Touloupas, Dimitrios
Nishimura, Naomi; Ragde, Prabhakar; Thilikos Touloupas, Dimitrios
Nishimura, Naomi; Prabhakar, Ragde; Thilikos Touloupas, Dimitrios
Nishimura, Naomi; Prabhakar, Ragde; Thilikos Touloupas, Dimitrios
Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Thilikos Touloupas, Dimitrios