The Vertex Separation and Search Number of a Graph
The Vertex Separation and Search Number of a Graph
复制标题
DOI：
10.1006/inco.1994.1064
复制
发表时间：
1994-08
期刊：
影响因子：
--
通讯作者：
J. Ellis;I. H. Sudborough;J. Turner
中科院分区：
文献类型：
--
作者：
J. Ellis;I. H. Sudborough;J. Turner
本文将图论中的两个概念与算法复杂性联系起来，即图的搜索数和顶点分离度。设s（G）表示连通无向图G的搜索数，vs（G）表示连通无向图G的顶点分离度。证明了vs（G）≤ s（G）≤ vs（G）+ 2，并给出了一个简单的G到G′的变换，使得vs（G′）= s（G）.我们刻画这些树具有给定的顶点分离，并描述了最小的这样的树。我们还注意到，存在搜索数和顶点分离之间的差确实是2的树。我们给出的算法，对于任何树T，计算VS（T）在线性时间和计算的最佳布局相对于顶点分离时间O（n log n）。顶点分离先前已经与渐进的黑色/白色卵石需求相关，并且已经被证明与搜索数量、节点搜索数量和路径宽度的变体相同，路径宽度与门矩阵布局成本相关。所有这些属性都是已知的计算上难以处理的。对于固定的k，一个O（n log 2 n）的算法是已知的，它决定了一个图是否有路径宽度最多为k。
Abstract We relate two concepts in graph theory and algorithmic complexity, namely the search number and the vertex separation of a graph. Let s ( 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′ such that vs ( G′ ) = s ( G ). We characterize those trees having a given vertex separation and describe the smallest such trees. We also note that there exist trees for which the difference between search number and vertex separation is indeed 2. We give algorithms 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 ). Vertex separation has previously been related to progressive black / white pebble demand and has been shown to be identical to a variant of search number, node search number , and to path width , which has been related to gate matrix layout cost . All these properties are known to be computationally intractable. For fixed k , an O ( n log 2 n ) algorithm is known which decides whether a graph has path width at most k .