2000/01/24 by Martin Grohe, Grohe, Martin · 1 citation
Computer Science · Mathematics · #05C83 #05C85 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph theory and applications #math.CO #msc:05C83 #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.math/0001128
arxiv created 2000/01/24 · openalex publication_date 2000/01/24 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The local tree-width of a graph G=(V,E) is the function ltwG: 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.