Graph Searching and a Min-Max Theorem for Tree-Width

1993/05/01 by Paul Seymour, P.D. Seymour, R. Thomas +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Computational Geometry and Mesh Generation #Corollary #Discrete mathematics #Geometry #Graph #Graph Theory and Algorithms #Line graph #Mathematics #Monotone polygon #Pairwise comparison #Pathwidth #Tree (set theory) #Treewidth

paper · doi:10.1006/jctb.1993.1027

crossref issued 1993/05/01 · crossref published 1993/05/01 · crossref published-print 1993/05/01 · openalex publication_date 1993/05/01 · crossref created 2002/09/18 · crossref deposited 2019/05/09 · openalex created_date 2025/10/10 · crossref indexed 2026/07/16 · openalex updated_date 2026/07/28

Citations

• Searching and pebbling
• Quickly excluding a forest
• Complexity of Finding Embeddings in a k -Tree

Cited by

• Directed Tree-Width
• The Gallai Vertex Problem is Θ₂^p-Complete
• Haven (graph theory) [wikipedia]