Search and sweep numbers of finite directed acyclic graphs (Q1208460): Difference between revisions

Let a graph be taken as representing a set of rooms (vertices) and corridors (edges). The searchers who move with fixed speed, have to find an infinitely fast intruder. The search number \(s(G)\) of a graph \(G\) is the least number of searchers required to find any intruder. The sweep number \(sw(G)\) is the least number of searchers required if the searchers and intruder are constrained to the vertices (e.g. the edges may represent doors between rooms). In the paper finite directed acyclic graphs are considered. A searcher may slide along an edge only in the indicated direction. It is shown that the search number for such graphs can be found in polynomial time. Tight bounds are given for the sweep number and it is determined exactly for two classes of graphs.