Algorithms and obstructions for linear-width and related search parameters
Algorithms and obstructions for linear-width and related search parameters
复制标题
线性宽度和相关搜索参数的算法和障碍
DOI：
10.1016/s0166-218x(00)00175-x
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
D. Thilikos
中科院分区：
文献类型：
--
作者：
D. Thilikos
图G的线宽定义为最小的整数k，使得G的边可以线性排列（e1，…，er），使得对于每一个i=1，…，r−1，最多有k个顶点关联到同时属于{e1，…，ei}和{ei+1，…，er}的边。本文给出了一个由57个图组成的集合，并证明了它是线性宽度最多为2的图的最小禁忌子集。我们的证明还给出了一个线性时间算法，该算法要么报告给定图的线性宽度大于2，要么输出最小线性宽度的边排序。我们进一步证明了线性宽度和混合搜索数之间的结构连接，这使我们能够为任何k或1确定具有线性宽度≥k的图类的无环禁止子集。此外，由于这种联系，我们的算法可以转换为两个线性时间算法，检查图是否有混合搜索或边搜索次数最多为两次，如果是，则构造相应的搜索移动序列。
The linear-width of a graph G is defined to be the smallest integer k such that the edges of G can be arranged in a linear ordering (e1,…,er) in such a way that for every i=1,…,r−1, there are at most k vertices incident to edges that belong both to {e1,…,ei} and to {ei+1,…,er}. In this paper, we give a set of 57 graphs and prove that it is the set of the minimal forbidden minors for the class of graphs with linear-width at most two. Our proof also gives a linear time algorithm that either reports that a given graph has linear-width more than two or outputs an edge ordering of minimum linear-width. We further prove a structural connection between linear-width and the mixed search number which enables us to determine, for any k⩾1, the set of acyclic forbidden minors for the class of graphs with linear-width⩽k. Moreover, due to this connection, our algorithm can be transfered to two linear time algorithms that check whether a graph has mixed search or edge search number at most two and, if so, construct the corresponding sequences of search moves.