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 条
  • [11] A tabu search approach to the optimal sequential partitions of directed acyclic graphs
    Kaji, T
    Ohuchi, A
    ELECTRICAL ENGINEERING IN JAPAN, 1997, 119 (04) : 42 - 51
  • [12] Acyclic Partitioning of Large Directed Acyclic Graphs
    Herrmann, Julien
    Kho, Jonathan
    Ucar, Bora
    Kaya, Kamer
    Catalyurek, Umit V.
    2017 17TH IEEE/ACM INTERNATIONAL SYMPOSIUM ON CLUSTER, CLOUD AND GRID COMPUTING (CCGRID), 2017, : 371 - 380
  • [13] Counting acyclic orderings in directed acyclic graphs
    Fox, Joseph
    Judd, Aimee
    Journal of Combinatorial Mathematics and Combinatorial Computing, 2020, 115 : 271 - 286
  • [14] Seepage in directed acyclic graphs
    Clarke, N. E.
    Finbow, S.
    Fitzpatrick, S. L.
    Messenger, M. E.
    Nowakowski, R. J.
    AUSTRALASIAN JOURNAL OF COMBINATORICS, 2009, 43 : 91 - 102
  • [15] ON MERGINGS IN ACYCLIC DIRECTED GRAPHS
    Han, Guangyue
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2019, 33 (03) : 1482 - 1502
  • [16] Contextual Directed Acyclic Graphs
    Thompson, Ryan
    Bonilla, Edwin, V
    Kohn, Robert
    INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 238, 2024, 238
  • [17] Functional Directed Acyclic Graphs
    Lee, Kuang-Yao
    Li, Lexin
    Li, Bing
    JOURNAL OF MACHINE LEARNING RESEARCH, 2024, 25 : 1 - 48
  • [18] Causal Directed Acyclic Graphs
    Lipsky, Ari M.
    Greenland, Sander
    JAMA-JOURNAL OF THE AMERICAN MEDICAL ASSOCIATION, 2022, 327 (11): : 1083 - 1084
  • [19] Directed Acyclic Graphs With Tears
    Chen Z.
    Ge Z.
    IEEE Transactions on Artificial Intelligence, 2023, 4 (04): : 972 - 983
  • [20] Treemaps for directed acyclic graphs
    Tsiaras, Vassilis
    Triantafilou, Sofia
    Tollis, Loannis G.
    GRAPH DRAWING, 2008, 4875 : 377 - 388
12345