Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418963 | Discrete Applied Mathematics | 2008 | 16 Pages |
Abstract
The four digraph search models, directed search, undirected search, strong search, and weak search, are studied in this paper. There are three types of actions for searchers in these models: placing, removing, and sliding. The four models differ in the abilities of searchers and intruders depending on whether or not they must obey the edge directions when they move along the directed edges. In this paper, we investigate the relationships between these search models. We introduce the concept of directed vertex separation for digraphs. We also discuss the properties of directed vertex separation, and investigate the relations between directed vertex separation, directed pathwidth and search numbers in different search models.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Boting Yang, Yi Cao,