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₁,...,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₁,...,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.