Title

Graph Separation and Search Number

Authors

J. A. Ellis, Washington University in St. Louis
H. Sudborough, University of Victoria
Jonathan S. Turner, Washington University in St. LouisFollow

Document Type

Technical Report

Publication Date

1987-05-01

Filename

WUCS-87-11.pdf

DOI:

10.7936/K77P8WQH

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)

Comments

Permanent URL: http://dx.doi.org/10.7936/K77P8WQH

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