- Title
- Monitoring the Edges of a Graph Using Distances
- Creator
- Foucaud, Florent; Klasing, Ralf; Miller, Mirka; Ryan, Joe
- Relation
- Conference on Algorithms and Discrete Applied Mathematics. Proceedings of the CALDAM 2020: the 6th International Conference on Algorithms and Discrete Applied Mathematics, Volume 12016 (Hyderabad, India 13-15 February, 2020) p. 28-40
- Publisher Link
- http://dx.doi.org/10.1007/978-3-030-39219-2_3
- Publisher
- Springer
- Resource Type
- conference paper
- Date
- 2020
- Description
- We introduce a new graph-theoretic concept in the area of network monitoring. A set M of vertices of a graph G is a distance-edge-monitoring set if for every edge e of G, there is a vertex x of M and a vertex y of G such that e belongs to all shortest paths between x and y. We denote by the smallest size of such a set in G. The vertices of M represent distance probes in a network modeled by G; when the edge e fails, the distance from x to y increases, and thus we are able to detect the failure. It turns out that not only we can detect it, but we can even correctly locate the failing edge. In this paper, we initiate the study of this new concept. We show that for a nontrivial connected graph G of order n, with if and only if G is a tree, and if and only if it is a complete graph. We compute the exact value of for grids, hypercubes, and complete bipartite graphs. Then, we relate to other standard graph parameters. We show that is lower-bounded by the arboricity of the graph, and upper-bounded by its vertex cover number. It is also upper-bounded by five times its feedback edge set number. Then, we show that determining for an input graph G is an NP-complete problem, even for apex graphs. There exists a polynomial-time logarithmic-factor approximation algorithm, however it is NP-hard to compute an asymptotically better approximation, even for bipartite graphs of small diameter and for bipartite subcubic graphs. For such instances, the problem is also unlikely to be fixed parameter tractable when parameterized by the solution size.
- Subject
- approximation algorithms; computational complexity; graphy algorithms; graphic methods; polynomial approximation
- Identifier
- http://hdl.handle.net/1959.13/1439555
- Identifier
- uon:40960
- Identifier
- ISBN:9783030392185
- Language
- eng
- Reviewed
- Hits: 1483
- Visitors: 510
- Downloads: 0