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 条
  • [41] Covering Pairs in Directed Acyclic Graphs
    Beerenwinkel, Niko
    Beretta, Stefano
    Bonizzoni, Paola
    Dondi, Riccardo
    Pirola, Yuri
    COMPUTER JOURNAL, 2015, 58 (07): : 1673 - 1686
  • [42] On counting homomorphisms to directed acyclic graphs
    Dyer, Martin
    Goldberg, Leslie Ann
    Paterson, Mike
    AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, 2006, 4051 : 38 - 49
  • [43] Transformers over Directed Acyclic Graphs
    Luo, Yuankai
    Thost, Veronika
    Shi, Lei
    ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 36 (NEURIPS 2023), 2023,
  • [44] Directed Acyclic Graphs in Surgical Research
    Gongola, AlleaBelle
    Bradshaw, Jace C.
    JOURNAL OF SURGICAL RESEARCH, 2023, 282 : 285 - 288
  • [45] Ternary directed acyclic word graphs
    Miyamoto, S
    Inenaga, S
    Takeda, M
    Shinohara, A
    THEORETICAL COMPUTER SCIENCE, 2004, 328 (1-2) : 97 - 111
  • [46] Sparse directed acyclic word graphs
    Inenaga, Shunsuke
    Takeda, Masayuki
    STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS, 2006, 4209 : 61 - 73
  • [47] Directed acyclic graphs in clinical research
    Dekkers, Olaf M.
    Laugesen, Kristina
    Groenwold, Rolf H. H.
    EUROPEAN JOURNAL OF ENDOCRINOLOGY, 2024, 190 (04) : E5 - E7
  • [48] Covering Pairs in Directed Acyclic Graphs
    Beerenwinkel, Niko
    Beretta, Stefano
    Bonizzoni, Paola
    Dondi, Riccardo
    Pirola, Yuri
    LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS (LATA 2014), 2014, 8370 : 126 - 137
  • [49] Cycle analysis of Directed Acyclic Graphs
    Vasiliauskaite, Vaiva
    Evans, Tim S.
    Expert, Paul
    PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2022, 596
  • [50] Model determination for directed acyclic graphs
    Consonni, G
    Leucari, V
    JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES D-THE STATISTICIAN, 2001, 50 : 243 - 256
12345