Near-Linear Query Complexity for Graph Inference

Sampath Kannan, Claire Mathieu, Hang Zhou

How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? Let $G=(V,E)$ be an unweighted, connected graph of bounded degree. The…