Solving sweeping problem for trees in graph theory

• Autorzy: Niwanthi W. A. L. , Panditharathne H. D. , Perera S. S. N.

Identyfikatory

DOI

10.5604/01.3001.0054.6288

Warianty tytułu

PL

Rozwiązywanie problemu przeczesywania drzew w teorii grafów

• Języki publikacji: EN

Abstrakty

EN

We develop a theory to determine the search number of a graph that allows us to detect an intruder along an edge without limiting the visibility of adjacent vertices. The presented technique here will allow to express the sweep problem as a linear program using an existing formulation of a linear program designed for problems where capture occurs only at a vertex of a graph. We also provide a method to solve the sweep problem for any complex tree, utilizing a set of sub-trees of the tree.

PL

Opracowano teorię wyznaczania liczby przeszukiwań grafu, która pozwala wykryć intruza wzdłuż krawędzi bez ograniczania widoczności sąsiednich wierzchołków. Przedstawiona technika pozwoli wyrazić problem przeczesywania grafu w postaci zadania programowania liniowego, wykorzystując istniejące sformułowanie programu liniowego przeznaczonego dla problemów, w których przechwytywanie następuje tylko w wierzchołku grafu. Przedstawiono również metodę rozwiązywania problemu przeczesywania dla dowolnego złożonego drzewa, wykorzystując zestaw poddrzew drzewa.

Słowa kluczowe

EN

search and sweep problem; set covering problem; branch cut algorithm; homeomorphic trees

PL

problem wyszukiwania i przeczesywania; problem pokrycia zestawu; algorytm wycinania gałęzi; drzewa homeomorficzne

• Wydawca: Institute of Computer and Information Systems, Faculty of Cybernetics, Military University of Technology
• Czasopismo: Computer Science and Mathematical Modelling
• Rocznik: 2023
• Tom: No. 17
• Strony: 29--33
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Niwanthi W. A. L.

• Department of Mathematics & Philosophy of Engineering, The Open University of Sri Lanka, Nawala, Nugegoda

autor

Panditharathne H. D.

• Department of Mathematics, University of Colombo, Colombo 03

autor

Perera S. S. N.

• Research & Development Center for Mathematical Modelling, Department of Mathematics, University of Colombo, Colombo 03

Bibliografia

• [1] Parsons T. D., “Pursuit-evasion in a graph”, [in:] Theory and applications of graphs, p. 426-441, Springer, 1978.
• [2] Alspach B., Dyer D., Hanson D., Yang B., “Time constrained graph searching”, Theoretical Computer Science, 399(3), 158-168 (2008).
• [3] Fomin F. V., Golovach P. A., Kratochvıl J., “On tractability of cops and robbers game”, Fifth IFIP International Conference on Theoretical Computer Science - TCS 2008”, IFIPAICT, vol. 273, 171-185, Springer, 2008.
• [4] Alspach B., “Searching and sweeping graphs: A brief survey”, Le matematiche, 59 (1, 2), 5-37 (2004).
• [5] Penuel J., Smith J. C., Shen S., “Models and complexity analysis for the graph decontamination problem with mobile agents”, Networks, vol. 61(1),1-19 (2013).
• [6] Chung T. H., Hollinger G. A., Isler V., “Search and pursuit-evasion in mobile robotics”, Autonomous robots, vol. 31(4), 299-316 (2011).
• [7] Kehagias A., Hollinger G., Singh S., “A graph search algorithm for indoor pursuit/evasion”, Mathematical and Computer Modelling, vol. 50(9-10), 1305-1317 (2009).
• [8] Megiddo N., Hakimi S. L., Garey M. R., D. S Johnson, Ch. H. Papadimitriou, “The complexity of searching a graph”, Journal of the ACM (JACM), vol. 35(1), 18-44 (1988).
• [9] Borie R., Tovey C., Koenig S., “Algorithms and complexity results for graph-based pursuit evasion”, Autonomous Robots, vol. 31(4), 317-332 (2011).
• [10] LaPaugh A. S., “Recontamination does not help to search a graph”, Journal of the ACM (JACM), vol. 40(2), 224-245 (1993).
• [11] Sheng-Lung Peng, Chin-Wen Ho, Tsan-Sheng Hsu, Ming-Tat Ko, Chuan Yi Tang, “Edge and node searching problems on trees”, Theoretical Computer Science, vol. 240(2), 429-446 (2008).
• [12] Caner Taşkin Z., Cole Smith J., “Branch--cut-price algorithms for solving a class of search problems on general graphs”, Networks, vol. 70(1), 4-18 (2017).
• [13] Lam E., Le Bodic P., Harabor D., Stuckey P. J., “Branch-and-cut-and-price for multi-agent path finding”, Computers & Operations Research, vol. 144, 105809 (2022).