Gwarantowanie bezpieczeństwa w systemie z połączeniami awaryjnymi

Abstract

We are considering security guaranteeing in systems with tree topology, augmented by additional backup links. A group of mobile autonomous agents needs to capture an invader, regardless of his strategy. In literature this problem is modeled as graph searching. We narrow the currently known search number estimation for cacti of degree 3 to two possible values for each number of branches with search number less than, or equal to $k$. We also classify type (**) branches, which have a hub or an avenue. Rozważamy zapewnianie bezpieczeństwa przed zewnętrznym intruzem w systemie o topologii drzewa, w którym wprowadzono dodatkowe połączenia awaryjne. Grupa mobilnych autonomicznych agentów musi przechwycić intruza, niezależnie od przyjętej przez niego strategii unikania. W literaturze problem ten jest modelowany jako przeszukiwanie grafów. W pracy zawężamy dotychczasowe oszacowanie na liczbę przeszukiwawczą kaktusów podkubicznych, do dwóch możliwych wartości dla każdej ilości odgałęzień z liczbą przeszukiwawczą nie większą niż $k$. Dokonujemy również pełnej klasyfikacji odgałęzień tzw. typu (**), posiadających rdzeń lub aleję.