Document Type
Technical Report
Publication Date
1987-05-01
Technical Report Number
WUCS-87-11
Abstract
We relate two concepts in graph theory and algorithmic complexity, namely the search number and the vertex separation of a graph. Lengauer has previously related vertex separation to progressive black/white pebble demand. Let a (G) denote the search number and vs(G) denote the vertex separation of a connected, undirected graph G. We show that vs(G) < s(G) < vs(G) +2 and we give a simple transformation from G to G^1 such that vs(G^1) = s(G). We give algorithm that, for any tree T, compute vs(T) in linear time and compute an optimal layout with respect to vertex separation in time O(n log n). We characterize those trees having a given vertex separation and describe the smallest such trees. We give an algorithm which, for all fixed k>1, decides the problem: "Is vs(G)
Recommended Citation
Ellis, J. A.; Sudborough, H.; and Turner, Jonathan S., "Graph Separation and Search Number" Report Number: WUCS-87-11 (1987). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/796
Comments
Permanent URL: http://dx.doi.org/10.7936/K77P8WQH