SEARCH AND SWEEP NUMBERS OF FINITE DIRECTED ACYCLIC GRAPHS

被引：6
|
作者：
NOWAKOWSKI, RJ
机构：
[1] Department of Mathematics, Statistics and Computing Science, Dalhousie University, Halifax
来源：
DISCRETE APPLIED MATHEMATICS | 1993年 / 41卷 / 01期
关键词：
D O I：
10.1016/0166-218X(93)90242-G
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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.
引用
收藏
页码：1 / 11
页数：11
相关论文
共 50 条
  • [31] Algebras associated to acyclic directed graphs
    Retakh, Vladimir
    Wilson, Robert Lee
    ADVANCES IN APPLIED MATHEMATICS, 2009, 42 (01) : 42 - 59
  • [32] Community detection in directed acyclic graphs
    Speidel, Leo
    Takaguchi, Taro
    Masuda, Naoki
    EUROPEAN PHYSICAL JOURNAL B, 2015, 88 (08):
  • [33] On counting homomorphisms to directed acyclic graphs
    Dyer, Martin
    Goldberg, Leslie Ann
    Paterson, Mike
    JOURNAL OF THE ACM, 2007, 54 (06)
  • [34] Recursive processing of directed acyclic graphs
    Bianchini, M
    Gori, M
    Scarselli, F
    NEURAL NETS WIRN VIETRI-01, 2002, : 96 - 101
  • [35] Ternary directed acyclic word graphs
    Miyamoto, S
    Inenaga, S
    Takeda, M
    Shinohara, A
    IMPLEMENTATION AND APPLICATION OF AUTOMATA, PROCEEDINGS, 2003, 2759 : 120 - 130
  • [36] HEURISTIC CHAINING IN DIRECTED ACYCLIC GRAPHS
    VENUGOPAL, R
    SRIKANT, YN
    COMPUTER LANGUAGES, 1993, 19 (03): : 169 - 184
  • [37] On compact directed acyclic word graphs
    Crochemore, M
    Verin, R
    STRUCTURES IN LOGIC AND COMPUTER SCIENCE: A SELECTION OF ESSAYS IN HONOR OF A. EHRENFEUCHT, 1997, 1261 : 192 - 211
  • [38] Broadcasting on Random Directed Acyclic Graphs
    Makur, Anuran
    Mossel, Elchanan
    Polyanskiy, Yury
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (02) : 780 - 812
  • [39] Information Flow on Directed Acyclic Graphs
    Donders, Michael
    More, Sara Miner
    Naumov, Pavel
    LOGIC, LANGUAGE, INFORMATION AND COMPUTATION, WOLLIC 2011, 2011, 6642 : 95 - 109
  • [40] Community detection in directed acyclic graphs
    Leo Speidel
    Taro Takaguchi
    Naoki Masuda
    The European Physical Journal B, 2015, 88
12345