Wyszukiwarka
Abstrakt
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.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Aktywność konferencyjna
- Typ:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Tytuł wydania:
- 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
- Język:
- angielski
- Rok wydania:
- 2008
- Opis bibliograficzny:
- 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:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1109/inftech.2008.4621646
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 49 razy