Integer programming model for distance-edge-monitoring problem
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Belgrade
2025-01-01
|
| Series: | Yugoslav Journal of Operations Research |
| Subjects: | |
| Online Access: | https://doiserbia.nb.rs/img/doi/0354-0243/2025/0354-02432400016K.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 0354-0243 1820-743X |