Parallel Network Mapping Algorithms
Ramtin Afshar, Michael T. Goodrich, Pedro Matias, Martha Carolina Osegueda · 2021
Motivated from parallel network mapping, we provide efficient query complexity and round complexity bounds for graph reconstruction using distance queries, including a bound that improves a previous sequential complexity bound. Our methods use a high-probability parametric parallelization of a graph clustering technique of Thorup and Zwick, which may be of independent interest.