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 条
  • [21] Copula directed acyclic graphs
    Eugen Pircalabelu
    Gerda Claeskens
    Irène Gijbels
    Statistics and Computing, 2017, 27 : 55 - 78
  • [22] Collapsibility for Directed Acyclic Graphs
    Xie, Xianchao
    Geng, Zhi
    SCANDINAVIAN JOURNAL OF STATISTICS, 2009, 36 (02) : 185 - 203
  • [23] Contextual Directed Acyclic Graphs
    Thompson, Ryan
    Bonilla, Edwin V.
    Kohn, Robert
    arXiv, 2023,
  • [24] Tutorial on directed acyclic graphs
    Digitale, Jean C.
    Martin, Jeffrey N.
    Glymour, Medellena Maria
    JOURNAL OF CLINICAL EPIDEMIOLOGY, 2022, 142 : 264 - 267
  • [25] Copula directed acyclic graphs
    Pircalabelu, Eugen
    Claeskens, Gerda
    Gijbels, Irene
    STATISTICS AND COMPUTING, 2017, 27 (01) : 55 - 78
  • [26] The incremental maintenance of a Depth-First-Search tree in directed acyclic graphs
    Franciosa, PG
    Gambosi, G
    Nanni, U
    INFORMATION PROCESSING LETTERS, 1997, 61 (02) : 113 - 120
  • [27] Monte Carlo Tree Search on Directed Acyclic Graphs for Object Pose Verification
    Bauer, Dominik
    Patten, Timothy
    Vincze, Markus
    COMPUTER VISION SYSTEMS (ICVS 2019), 2019, 11754 : 386 - 396
  • [28] MULTILEVEL ALGORITHMS FOR ACYCLIC PARTITIONING OF DIRECTED ACYCLIC GRAPHS
    Herrmann, Julien
    Ozkaya, M. Yusuf
    Ucar, Bora
    Kaya, Kamer
    Catalyurek, Umit, V
    SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2019, 41 (04): : A2117 - A2145
  • [29] Acyclic and oriented chromatic numbers of graphs
    Kostochka, AV
    Sopena, E
    Zhu, X
    JOURNAL OF GRAPH THEORY, 1997, 24 (04) : 331 - 340
  • [30] LCA queries in directed acyclic graphs
    Kowaluk, M
    Lingas, A
    AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS, 2005, 3580 : 241 - 248
12345