Non-monotone graph searching models

• Autorzy: Ostrowski R.

Warianty tytułu

PL

Niemonotoniczne modele przeszukiwania grafów

• Języki publikacji: EN

Abstrakty

EN

Graph searching encompasses a variety of different models, many of which share a property that in optimal strategies fugitive can never access once searched regions. Monotonicity, as it is called, is vital in many established results in the field however its absence significantly impedes the analysis of a given problem. This survey attempts to gather non-monotone models, that are less researched in effort of summarizing the results concerning them and open questions left.

PL

Przeszukiwanie grafów obejmuje wiele modeli, z których wiele dzieli własność, że w optymalnych strategiach uciekinier nie może dostać się ponownie do raz przeszukanych obszarów. Własność ta, nazwana monotonicznością, jest istotna w wielu osiągnięciach dziedziny i jej brak znacząco utrudnia analizę problemów. Ten przegląd ma na celu zebranie niemonotonicznych modeli, które są mniej zbadane w celu podsumowania rezultatów i otwartych pytań.

Słowa kluczowe

EN

non-monotone model; searching graphs

PL

model niemonotoniczny; przeszukiwanie grafów

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2018
• Tom: T. 23
• Strony: 90--96
• Opis fizyczny: Bibliogr. 34 poz.

Twórcy

autor

Ostrowski R.

• Faculty of Electronics, Telecommunications and Informatics, Gdańsk University of Technology, Poland

Bibliografia

• [1] Parsons T. D.: Pursuit-evasion in a graph. Theory and applications of graphs. Springer, Berlin, Heidelberg, 1978. s.426-441.
• [2] LaPaugh A. S.: Recontamination does not help to search a graph. Journal of the ACM (JACM), 1993, 40(2), s.224-245.
• [3] Aigner M., Fromme M.: A game of cops and robbers. Discrete Applied Mathematics, 1984, 8(1), s.1-12.
• [4] Berwanger D., Dawar A., Hunter P., Kreutzer S.: DAG-width and parity games. In STACS February 2006 , Vol. 6, s.524-536.
• [5] Richerby D., Thilikos D. M.: Graph searching in a crime wave. SIAM Journal on Discrete Mathematics, 2009, 23(1), s.349-368.
• [6] Mazoit F., Nisse N.: Monotonicity of non-deterministic graph searching. Theoretical Computer Science, 2008, 399(3), s.169-178.
• [7] Seymour P. D., Thomas R.: Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B, 1993, 58(1), s.22-33.
• [8] Dendris N. D., Kirousis L. M., Thilikos D. M.: Fugitive-search games on graphs and related parameters. Theoretical Computer Science, 1997, 172(1-2), s.233-254.
• [9] Dyer D., Yang B., Yaşar Ö.: On the fast searching problem. In International Conference on Algorithmic Applications in Management. Springer, Berlin, Heidelberg., June 2008, s.143-154
• [10] Kreutzer S., Ordyniak S.: Distance d-Domination Games. In WG, December 2009, s.308-319.
• [11] Kreutzer S., Ordyniak S.: Complexity and monotonicity results for domination games. Theoretical Computer Science, 2016, 628, s.1-29.
• [12] Amiri S. A., Kreutzer S., Rabinovich R.: DAG-width is PSPACE-complete. Theoretical Computer Science, 2016, 655, s.78-89.
• [13] Yang B., Cao Y.: Monotonicity in digraph search problems. Theoretical Computer Science, 2008, 407(1), s.532-544.
• [14] Ilcinkas D., Nisse N., Soguet D.: The cost of monotonicity in distributed graph searching. Distributed Computing, 2009, 22(2), s.117-127.
• [15] Fraigniaud P., Nisse N.: Monotony properties of connected visible graph searching. Information and Computation, 2008, 206(12), s.1383-1393.
• [16] Dereniowski D., Dyer D., Tifenbach R. M., Yang B.: Zero-visibility cops and robber and the pathwidth of a graph. J. Comb. Optim., 2015, 29(3), s.541-564.
• [17] Adler I.: Marshals, monotone marshals, and hypertree‐width. Journal of Graph Theory, 2004, 47(4), s.275-296.
• [18] Obdrzálek J.: DAG-width: connectivity measure for directed graphs. In: Proceedings of the Seventeenth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22–26, 2006, ACM Press, 2006, s.814–821.
• [19] Hunter P., Kreutzer S.: Digraph measures: Kelly decompositions, games, and orderings, Theoretical Computer Science, 2008, 399 (3), s.206–219
• [20] Kreutzer S., Ordyniak S.: Digraph decompositions and monotonicity in digraph searching. Theoretical Computer Science, 2011, 412(35), 4688-4703.
• [21] Yang B., Cao Y.: Directed searching digraphs: monotonicity and complexity. In: TAMC, May 2007, s.136-147.
• [22] Yang, B., Cao, Y.: Monotonicity of strong searching on digraphs. Journal of Combinatorial Optimization, 2007, 14(4), 411-425.
• [23] Yang, B., Cao, Y.: On the monotonicity of weak searching. Computing and Combinatorics, 2008, s.52-61.
• [24] Alspach B., Dyer D., Hanson D., Yang, B.: Arc searching digraphs without jumping, Lecture Notes in Computer Science, 2007, 4616, 354.
• [25] Barriere L., Fraigniaud P., Santoro N., Thilikos D. M.: Searching is not jumping. In: International Workshop on Graph-Theoretic Concepts in Computer Science, June 2003, Springer, Berlin, Heidelberg, s.34-45.
• [26] Yang B., Dyer D., Alspach B.: Sweeping graphs with large clique number, Disc. Math., 2009, 309, s.5770–5780.
• [27] Dereniowski, D.: From pathwidth to connected pathwidth, SIAM Journal on Discrete Mathematics, 2012, 26(4), s.1709-1732.
• [28] Best M. J., Gupta A., Thilikos D. M., Zoros D.: Contraction obstructions for connected graph searching. Discrete Applied Mathematics, 2016, 209, s.27-47.
• [29] Blin L., Fraigniaud P., Nisse N.,Vial S.: Distributed chasing of network intruders. Theor. Comput. Sci., 2008, 399(1- 2), s.12–37,.
• [30] Flocchini P., Santoro N.: Distributed security algorithms for mobile agents. Mobile Agents in Networking and Distributed Computing, 2012, s.41-70.
• [31] Blin L., Burman J., Nisse N.: Perpetual graph searching, Doctoral dissertation, INRIA, 2012.
• [32] Blin L., Burman J., Nisse N.: Exclusive graph searching. Algorithmica, 2017, 77(3), s.942-969.
• [33] Markou E., Nisse N., Pérennes S.: Exclusive graph searching vs. pathwidth. Information and Computation, 2017, 252, s. 243-260.
• [34] Dereniowski D.: Maximum vertex occupation time and inert fugitive: Recontamination does help. Information Processing Letters, 2009, 109(9), s. 422-426.