@inproceedings{0f73d5d6531b4deb970384e55c748f2e,
title = "Quasi-Linear Distance Query Reconstruction for Graphs of Bounded Treelength",
abstract = "In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices u and v, the oracle returns the shortest path distance between u and v in the graph. The length of a tree decomposition is the maximum distance between two vertices contained in the same bag. The treelength of a graph is defined as the minimum length of a tree decomposition of this graph. We present an algorithm to reconstruct an n-vertex connected graph G parameterized by maximum degree ∆ and treelength k in Ok∆(nlog2 n) queries (in expectation). This is the first algorithm to achieve quasi-linear complexity for this class of graphs. The proof goes through a new lemma that could give independent insight on graphs of bounded treelength.",
keywords = "Distance Reconstruction, Randomized Algorithm, Treelength",
author = "Paul Bastide and Carla Groenland",
year = "2024",
doi = "10.4230/LIPIcs.IPEC.2024.20",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Edouard Bonnet and Pawel Rzazewski",
booktitle = "19th International Symposium on Parameterized and Exact Computation, IPEC 2024",
address = "Germany",
note = "19th International Symposium on Parameterized and Exact Computation, IPEC 2024 ; Conference date: 04-09-2024 Through 06-09-2024",
}