Local tree-width, excluded minors, and approximation algorithms
| dc.creator | Grohe, Martin | |
| dc.date | 2000-01-24 | |
| dc.date.accessioned | 2026-07-07T04:33:24Z | |
| dc.date.available | 2026-07-07T04:33:24Z | |
| dc.description | The local tree-width of a graph G=(V,E) is the function ltw^G: N -> N that associates with every natural number r the maximal tree-width of an r-neighborhood in G. Our main graph theoretic result is a decomposition theorem for graphs with excluded minors that essentially says that such graphs can be decomposed into trees of graphs of bounded local tree-width. As an application of this theorem, we show that a number of combinatorial optimization problems, such as Minimum Vertex Cover, Minimum Dominating Set, and Maximum Independent Set have a polynomial time approximation scheme when restricted to a class of graphs with an excluded minor. | |
| dc.identifier | https://arxiv.org/abs/math/0001128 | |
| dc.identifier | http://arxiv.org/abs/math/0001128 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/58562 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C83, 05C85, 68R10 | |
| dc.title | Local tree-width, excluded minors, and approximation algorithms | |
| dc.type | text |