The Vertex Separation and Search Number of a Graph

1994/08/01 by John Ellis, J.A. Ellis, I. Hal Sudborough +3 · 14 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Feedback vertex set #Graph #Interconnection Networks and Systems #Mathematics #Time complexity #Vertex (graph theory)

paper · doi:10.1006/inco.1994.1064

crossref issued 1994/08/01 · crossref published 1994/08/01 · crossref published-print 1994/08/01 · openalex publication_date 1994/08/01 · crossref created 2002/09/17 · crossref deposited 2019/05/08 · openalex created_date 2025/10/10 · crossref indexed 2026/02/06 · openalex updated_date 2026/07/28

Citations

• Applications of a Planar Separator Theorem
• Nonconstructive tools for proving polynomial-time decidability
• Black-white pebbles and graph separation
• Complexity of Finding Embeddings in a k-Tree

Cited by

• An annotated bibliography on guaranteed graph searching
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• Pathwidth of outerplanar graphs
• Pathwidth of Planar and Line Graphs
• Approximation of pathwidth of outerplanar graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A simple linear-time algorithm for finding path-decompositions of small width
• A Distributed Algorithm for Computing the Node Search Number in Trees
• Computing Optimal Linear Layouts of Trees in Linear Time
• Pathwidth of Circular-Arc Graphs
• Obstruction set isolation for the gate matrix layout problem
• Pathwidth [wikipedia]
• Pursuit–evasion [wikipedia]