Integer Programming Model for Distance-Edge-Monitoring Problem

Abstract

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.

Published
2024-05-12
How to Cite
KARTELJ, Aleksandar; FILIPOVIĆ, Vladimir; KRATICA, Jozef. Integer Programming Model for Distance-Edge-Monitoring Problem. Yugoslav Journal of Operations Research, [S.l.], may 2024. ISSN 2334-6043. Available at: <https://yujor.fon.bg.ac.rs/index.php/yujor/article/view/1271>. Date accessed: 14 dec. 2024. doi: https://doi.org/10.2298/YJOR230815016K.
Section
Research Articles

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.