Computing Small Search Numbers in Linear Time

摘要

Let G = (V, E) be a graph. The linear-width of G is defined as the smallest integer k such that E can be arranged in a linear ordering (e_1,.. .,e_r) such that for every i = 1,.. .,r-1, there are at most k vertices both incident to an edge that belongs to {e_1,...,e_i} and to an edge that belongs to {e_(i+1),... ,e_r}. For each fixed constant k, a linear time algorithm is given, that decides for any graph G = (V, E) whether the linear-width of G is at most k, and if so, finds the corresponding ordering of E. Linear-width has been proved to be related with the following graph searching parameters: mixed search number, node search number, and edge search number. A consequence of this is that we obtain for fixed k, linear time algorithms that check whether a given graph can be mixed, node, or edge searched with at most k searchers, and if so, output the corresponding search strategies.