Near-Linear Query Complexity for Graph Inference
From MaRDI portal
Publication:3448836
DOI10.1007/978-3-662-47672-7_63zbMath1440.68124arXiv1402.4037OpenAlexW1607651383MaRDI QIDQ3448836
Hang Zhou, Claire Mathieu, Sampath Kannan
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.4037
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Information storage and retrieval of data (68P20) Randomized algorithms (68W20)
Cites Work
- Unnamed Item
- On the longest path algorithm for reconstructing trees from distance matrices
- An optimal algorithm to reconstruct trees from additive distance data
- Approximation algorithms for combinatorial problems
- Distance realization problems with applications to internet tomography
- Exploring networks with traceroute-like probes: Theory and simulations
- Network tomography: recent developments
- Network Discovery and Verification with Distance Queries
- Graph Reconstruction via Distance Oracles
- Graph-Theoretic Concepts in Computer Science
- On the bias of traceroute sampling