×

Graph covering via shortest paths. (English) Zbl 1137.05056

This paper defines two related graph covering problems motivated by network monitoring. Both problems related to the idea of graph measurement from a single vertex via shortest paths, and are meant to serve as lower and upper bounds on the amount of information that can be gained by measuring a graph via shortest paths. This paper shows that the minimization problem for each model is NP-hard, and then enumerates several classes of graphs for which the minimization problems are efficiently solvable.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
PDFBibTeX XMLCite