We introduce a new graph-theoretic concept in the area of network monitoring. In this area, one wishes to monitor the vertices and/or the edges of a network (viewed as a graph) in order to detect and prevent failures. Inspired by two notions studied in the literature (edge-geodetic sets and distance-edge-monitoring sets), we define the notion of a monitoring edge-geodetic set (MEG-set for short) of a graph G as an edge-geodetic set S ⊆ V ( G ) of G (that is, every edge of G lies on some shortest path between two vertices of S ) with the additional property that for every edge e of G , there is a vertex pair x , y of S such that e lies on all shortest paths between x and y . The motivation is that, if some edge e is removed from the network (for example if it ceases to function), the monitoring probes x and y will detect the failure since the distance between them will increase. We explore the notion of MEG-sets by deriving the minimum size of a MEG-set for some basic graph classes (trees, cycles, unicyclic graphs, complete graphs, grids, hypercubes, corona products...) and we prove an upper bound using the feedback edge set of the graph. We also show that determining the smallest size of an MEG-set of a graph is NP-hard, even for graphs of maximum degree at most 9.

We present a linear time algorithm for the weighted k -center problem on trees for fixed k . This partially settles the long-standing question about the lower bound on the time complexity of the problem. The current time complexity of the best-known algorithm for the problem with k as part of the input is O ( n log ⁡ n ) by Wang et al. (2018) [20] . Whether an O ( n ) time algorithm exists for arbitrary k is still open.