Integer Programming Model for Distance-Edge-Monitoring Problem
DOI:
https://doi.org/10.2298/YJOR230815016KKeywords:
Distance-edge-monitoring problem, network monitoring, dem number, integer programming, combinatorial optimizationAbstract
The paper considers the recently introduced distance-edge-monitoring problem. For a given graph G = (V,E), the set M is called distance-edge-monitoring if it is a subset of V and for every edge e of E there is a vertex x of M and a vertex y of V such that e belongs to all the shortest paths between x and y. The goal is to find the smallest distance-edge-monitoring set of the graph. We propose the first-ever integer programming model for this problem and present empirical results for five instance classes with graphs up to 4096 vertices and 1599797 edges. The proposed model was able to solve all instances of four instance classes optimally, while the remaining fifth class of graphs proves to be more difficult for the proposed model.References
F. Foucaud, S.-S. Kao, R. Klasing, M. Miller, and J. Ryan, “Monitoring the edges of a graph using distances,” Discrete Appl. Math., vol. 319, pp. 424-438, 2022.
R. Govindan and H. Tangmunarunkit, “Heuristics for internet map discovery,” in Proc IEEE INFOCOM 2000, vol. 3. IEEE, 2000, pp. 1371-1380.
L. Dall’Asta, I. Alvarez-Hamelin, A. Barrat, A. Vázquez, and A. Vespignani, “Exploring networks with traceroute-like probes: Theory and simulations,” Theor. Comput. Sci., vol. 355, no. 1, pp. 6-24, 2006.
Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihal’ak, and L. S. Ram, “Network discovery and verification,” IEEE J. Sel. Areas Commun., vol. 24, no. 12, pp. 2168- 2181, 2006.
D. Bilò, T. Erlebach, M. Mihalák, and P. Widmayer, “Discovery of network properties with all-shortest-paths queries,” Theor. Comput. Sci., vol. 411, no. 14-15, pp. 1626-1637, 2010.
E. Bampas, D. Bil`o, G. Drovandi, L. Gual`a, R. Klasing, and G. Proietti, “Network verification via routing table queries,” J. Comput. Syst. Sci., vol. 81, no. 1, pp. 234-248, 2015.
W. Li, R. Klasing, Y. Mao, and B. Ning, “Monitoring the edges of product networks using distances,” arXiv preprint arXiv:2211.10743, 2022.
C. Yang, R. Klasing, Y. Mao, and X. Deng, “On the distance-edge-monitoring numbers of graphs,” Discrete Appl. Math., vol. 342, pp. 153-167, 2024. doi: https://doi.org/10.1016/j.dam.2023.09.012
C. Yang, R. Klasing, C. He, and Y. Mao, “Perturbation results for distance-edge-monitoring numbers,” arXiv preprint arXiv:2301.02507, 2023.
G. Yang and C. He, “Distance-edge-monitoring sets in hierarchical and corona graphs,” J. Interconnect. Netw., vol. 23, no. 02, p. 2250003, 2023.
L. Václav, “Distance edge monitoring set problem with respect to structural parameters,” B.S. thesis, Faculty of Information Technology CTU in Prague, Department of Theoretical Computer Science, 2022.
F. Foucaud, K. Narayanan, and L. Ramasubramony Sulochana, “Monitoring edge-geodetic sets in graphs,” in Conf. Algorithms Discrete Appl. Math. Springer, 2023, pp. 245-256.
J. Haslegrave, “Monitoring edge-geodetic sets: hardness and graph products,” Discrete Appl. Math., vol. 340, pp. 79-84, 2023.
A. Tan, W. Li, X. Wang, and X. Li, “Monitoring edge-geodetic numbers of convex polytopes and four networks,” Int. J. Parallel Emergent Distrib. Syst., pp. 1-12, 2023.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
