Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries

Chirag Kaudan, Amir Nayyeri

We consider the following graph reconstruction problem: given an unweighted connected graph $G=(V,E)$ with visible vertex set $V$ and an oracle which takes two vertices $u,v \in…