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

• Autorzy: Wrona Ł.

Warianty tytułu

EN

Security guaranteeing in systems with backup links

• Języki publikacji: PL

Abstrakty

PL

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ę.

EN

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.

Słowa kluczowe

PL

przeszukiwanie grafów; złożoność obliczeniowa; bezpieczeństwo systemów; kaktus

EN

graph searching; computational complexity; search number; system security; cacti

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 663--671
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Wrona Ł.

• Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska

Bibliografia

• [1] Parsons T.D., Pursuit-evasion in a graph. Lecture Notes in Mathematics, 642, 1976, 426.
• [2] LaPaugh A., Recontamination does not help to search a graph. J. ACM, 40, 1993, 224.
• [3] Wrona L., Scanning Networks with Cactus Topology. Proceedings of the 1st International Conference on Information Technology, 2008, 301.
• [4] Wrona L., Metody przechwytywania poruszających się obiektów przez mobilnych agentów. Praca magisterska, Politechnika Gdańska, Wydział ETI, 2006.
• [5] Fomin V.F., Thilikos M.D., An annotated bibliography on guaranteed graph searching. Theor. Comput. Sei., 399(3), 2008, 236.
• [6] Megiddo N., Hakimi S.L., Garey M.R., Johnson D.S., Papadimitriou C.H., The Complexity of Searching a Graph. J. ACM., 35, 1988, 18.
• [7] Peng S.-L., Ho C.-W., Ко M.-T., Tang C.Y., Edge and node searching problems on trees. Theor. Comput. Sci., 240(2), 2000, 429.