Fast searching on cactus graphs

Springer Science and Business Media LLC - 2023
Yuan Xue1, Boting Yang1, Sandra Zilles1, Lusheng Wang2,3
1Department of Computer Science, University of Regina, Regina, Canada
2Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, China
3City University of Hong Kong Shenzhen Research Institution, Shenzhen, China

Tóm tắt

The problem of finding the fast search number of a graph is NP-complete. It is challenging even when the graph has very small treewidth. However, it can be much easier to find an optimal fast search strategy for smaller subgraphs with special properties. This observation motivates us to establish relationships between optimal fast search strategies for a graph and its subgraphs although fast searching does not have the subgraph-closed property. In this paper, we introduce the notion of k-combinable graphs and study their properties. We propose a new method for computing the fast search number of k-combinable graphs. As an application of this method, we examine the fast searching for cactus graphs. We investigate the properties of optimal fast search strategies and give a linear time algorithm for computing the fast search number of cactus graphs.

Từ khóa


Tài liệu tham khảo

Alspach B (2006) Sweeping and searching in graphs: a brief survey. Matematiche 59:5–37

Bienstock D (1991) Graph searching, path-width, tree-width and related problems (a survey). DIMACS Ser Discr Math Theoret Comput Sci 5:33–49

Bienstock D, Seymour P (1991) Monotonicity in graph searching. J Algorithms 12:239–245

Bonato A, Nowakowski R (2011) The Game of Cops and Robbers on Graphs. American Mathematical Society, Providence, Rhode Island

Bonato A, Yang B (2013) Graph searching and related problems. In: Pardalos P, Du D-Z and Graham R (eds) Handbook of Combinatorial Optimization, pp 1511–1558. Springer, 2nd edition

Dereniowski D, Diner Ö, Dyer D (2013) Three-fast-searchable graphs. Discr Appl Math 161:1950–1958

Dyer D, Yang B, Yaşar Ö (2008) On the fast searching problem. In: Algorithmic Aspects in Information and Management, pp 143–154. Springer

Fomin FV, Petrov NN (1996) Pursuit-evasion and search problems on graphs. Congressus Numerantium, pp 47–58

Fomin FV, Thilikos DM (2008) An annotated bibliography on guaranteed graph searching. Theor Comput Sci 399:236–245

Hahn G (2007) Cops, robbers and graphs. Tatra Mt Math Publ 36:163–176

Kirousis LM, Papadimitriou CH (1986) Searching and pebbling. Theor Comput Sci 47:205–218

LaPaugh A (1993) Recontamination does not help to search a graph. J ACM 40:224–245

Makedon FS, Papadimitriou CH, Sudborough IH (1985) Topological bandwidth. SIAM J Algebr Discr Methods 6:418–444

Megiddo N, Hakimi SL, Garey MR, Johnson DS, Papadimitriou CH (1988) The complexity of searching a graph. J ACM 35:18–44

Parsons TD (1976) Pursuit-evasion in a graph. In: Proceedings of the International Conference on the Theory and Applications of Graphs, Lecture Notes in Mathematics, pp 426–441. Springer-Verlag

Stanley D, Yang B (2011) Fast searching games on graphs. J Comb Optim 22:763–777

Xue Y, Yang B (2017) The fast search number of a cartesian product of graphs. Discr Appl Math 224:106–119

Xue Y, Yang B, Zhong F, Zilles S (2018) The fast search number of a complete \(k\)-partite graph. Algorithmica 80:3959–3981

Yang B (2011) Fast edge searching and fast searching on graphs. Theoret Comput Sci 412:1208–1219

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Thông tin tác giả