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.