Repozytorium publikacji - Politechnika Gdańska

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.

Autorzy

• Łukasz Wrona