The vertex separation number of a graph equals its path-width

1992/07/01 by Nancy Kinnersley, Nancy G. Kinnersley · 7 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Mathematics #Optimization and Search Problems #Path (computing) #Vertex (graph theory)

paper · doi:10.1016/0020-0190(92)90234-m

crossref issued 1992/07/01 · crossref published 1992/07/01 · crossref published-print 1992/07/01 · openalex publication_date 1992/07/01 · crossref created 2002/07/26 · crossref deposited 2019/04/13 · openalex created_date 2025/10/10 · crossref indexed 2026/06/11 · openalex updated_date 2026/07/23

Citations

• Nonconstructive tools for proving polynomial-time decidability
• Searching and pebbling
• Black-white pebbles and graph separation

Cited by

• Pathwidth of outerplanar graphs
• Pathwidth of Planar and Line Graphs
• A Distributed Algorithm for Computing the Node Search Number in Trees
• Computing Optimal Linear Layouts of Trees in Linear Time
• Inapproximability of Treewidth and Related Problems
• Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
• Pathwidth [wikipedia]