Search and sweep numbers of finite directed acyclic graphs
type: Item
instance of: scholarly article
title: Search and sweep numbers of finite directed acyclic graphs
zbMATH Open document ID: 0777.05062
DOI: 10.1016/0166-218X(93)90242-G
published in: Discrete Applied Mathematics
publication date: 1993-05-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 90B40
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 166461
zbMATH Keywords: search number
zbMATH Keywords: sweep number
zbMATH Keywords: directed acyclic graphs
author: R. J. Nowakowski
reviewed by: Vladimir Fleischer
MaRDI profile type: Publication
cites work: Combinatorial theory.
cites work: A game of cops and robbers
cites work: Compact Spaces and Spaces of Maximal Complete Subgraphs
cites work: Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
cites work: A decomposition theorem for partially ordered sets
cites work: Searching and pebbling
cites work: The complexity of searching a graph
cites work: Vertex-to-vertex pursuit in a graph
cites work: Q4739657
cites work: Q4159394
cites work: Q3208679
cites work: Antichain cutsets
description: scientific article; zbMATH DE number 166461