Search and sweep numbers of finite directed acyclic graphs

Search and sweep numbers of finite directed acyclic graphs

0.00 Avg rating0 Votes
Article ID: iaor19931474
Country: Netherlands
Volume: 41
Issue: 1
Start Page Number: 1
End Page Number: 11
Publication Date: Jan 1993
Journal: Discrete Applied Mathematics
Authors:
Keywords: search
Abstract:

The search number of a graph is the least number of searchers needed to find any (possibly infinitely fast) intruder hiding in the vertices or edges of the graph. The sweep number 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 a directed acyclic graph the searchers are allowed to traverse the edges only in the given direction. The search number for directed acyclic graphs is determined. Bounds are given for the sweep number and it is determined exactly for two classes of directed acyclic graphs.

Reviews

Required fields are marked *. Your email address will not be published.