Search
Abstract
The family of Pursuit and Evasion problems is widelystudied because of its numerous practical applications,ranging from communication protocols to cybernetic andphysical security. Calculating the search number of a graphis one of most commonly analyzed members of this problemfamily. The search number is the smallest number of mobileagents required to capture an invisible and arbitrarily fastfugitive, for instance piece of malicious software, in a givengraph. It is closely related to some other well known graphparameters, such as treewidth and pathwidth, and has beenstudied in a wide range of variants (edge, node, mixed,monotonous, connected, distributed, and others). Calculatingthe edge search number of a general graph is NPhard,while it can be computed in linear time for trees. Calculatingthe search number of cacti, however, has not yetbeen widely covered. In this work we focus on this classof graphs, as it may be used to model Token Ring networksas well as some other network topologies when we assumethat backup links are present. We address the problem ofcalculating the search number, as well as generating searchstrategy for cacti.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Conference activity
- Type:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Title of issue:
- Proceedings of the 2008 1st International Conference on Information Technology, Gdansk, 19-21 May, 2008, Poland, Gdansk University of Technology, Faculty of Electronics, Telecommunications and Informatics strony 301 - 306
- Language:
- English
- Publication year:
- 2008
- Bibliographic description:
- Wrona Ł.: Scanning networks with cactus topology// Proceedings of the 2008 1st International Conference on Information Technology, Gdansk, 19-21 May, 2008, Poland, Gdansk University of Technology, Faculty of Electronics, Telecommunications and Informatics/ ed. eds: A. Stepnowski [et al.]. Gdansk: Gdansk University of Technology, 2008, s.301-306
- DOI:
- Digital Object Identifier (open in new tab) 10.1109/inftech.2008.4621646
- Verified by:
- Gdańsk University of Technology
seen 53 times