Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915853553893376 |
|---|---|
| author | Kaudan, Chirag Nayyeri, Amir |
| author_facet | Kaudan, Chirag Nayyeri, Amir |
| contents | 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 V$ and returns the shortest path distance between $u$ and $v$, how many queries are needed to reconstruct $E$?
Specifically, we consider bounded degree $Δ$ and bounded treelength $\mathrm{tl}$ connected graphs and show that reconstruction can be done in $O_{Δ,\mathrm{tl}}(n \log n)$ queries with a deterministic algorithm. This result improves over the best known algorithm (deterministic or randomized) for this graph class by a $\log n$ factor and matches the known lower bound for the class of graphs with bounded chordality, which is a subclass of bounded treelength graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_10432 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries Kaudan, Chirag Nayyeri, Amir Data Structures and Algorithms G.2.2 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 V$ and returns the shortest path distance between $u$ and $v$, how many queries are needed to reconstruct $E$? Specifically, we consider bounded degree $Δ$ and bounded treelength $\mathrm{tl}$ connected graphs and show that reconstruction can be done in $O_{Δ,\mathrm{tl}}(n \log n)$ queries with a deterministic algorithm. This result improves over the best known algorithm (deterministic or randomized) for this graph class by a $\log n$ factor and matches the known lower bound for the class of graphs with bounded chordality, which is a subclass of bounded treelength graphs. |
| title | Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries |
| topic | Data Structures and Algorithms G.2.2 |
| url | https://arxiv.org/abs/2603.10432 |