Graph Reconstruction via Distance Oracles

2013/04/24 by Mathieu, Claire, Zhou, Hang · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1304.6588

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.

Cited by

• Complexity of learning matchings and half graphs via edge queries
• Toward a Graph Foundation Model: Pre-Training Transformers With Random Walks

Related

• Graph Reconstruction with a Connected Components Oracle
• Optimal distance query reconstruction for graphs without long induced cycles
• Quasi-linear distance query reconstruction for graphs of bounded treelength
• Near-Linear Query Complexity for Graph Inference
• Distance Reconstruction of Sparse Random Graphs