@inproceedings{d00fb9a48a014745a283df6ac000ea14,
title = "Graph reconstruction via distance oracles",
abstract = "We study the problem of reconstructing a hidden graph given access to a distance oracle. We design randomized algorithms for the following problems: reconstruction of a degree bounded graph with query complexity {\~O}(n 3/2); reconstruction of a degree bounded outerplanar graph with query complexity {\~O}(n); and near-optimal approximate reconstruction of a general graph.",
author = "Claire Mathieu and Hang Zhou",
year = "2013",
month = jul,
day = "23",
doi = "10.1007/978-3-642-39206-1\_62",
language = "English",
isbn = "9783642392054",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
number = "PART 1",
pages = "733--744",
booktitle = "Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings",
edition = "PART 1",
note = "40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 ; Conference date: 08-07-2013 Through 12-07-2013",
}