Graph Covering via Shortest Paths

摘要

We define two related graph covering problems motivated by network monitoring. Both problems relate 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. We show that the minimization problem for each model is NP-hard, and then we enumerate several classes of graphs for which the minimization problems are efficiently solvable.