Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
- Sesja wygasła!
Identyfikatory
Warianty tytułu
Security guaranteeing in systems with backup links
Języki publikacji
Abstrakty
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ę.
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.
Wydawca
Rocznik
Tom
Strony
663--671
Opis fizyczny
Bibliogr. 7 poz., rys.
Twórcy
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-AGH1-0020-0062