For a source node, \(v\), and target node, \(w\),
the traceroute command iteratively issues
“\(k\)th-hop” queries, for \(k=1, 2, \dots, \delta(v,w)\),
which return the name of the \(k\)th vertex on a shortest path from
\(v\) to \(w\), where \(\delta(v,w)\) is the distance between \(v\) and
\(w\), that is, the number of edges in a shortest-path from \(v\) to
\(w\). The traceroute command is often used for network
mapping applications and it has been studied theoretically with respect
to biases it introduces for network mapping when only a subset of nodes
in the network can be the source of traceroute queries. We
are not aware of prior theoretical work on efficient network mapping
algorithms, however, that are based on
\(k\)th-hop traceroute queries; hence, in this paper we
provide such algorithms. Our results include an algorithm that runs in
a constant number of parallel rounds with a subquadratic number of
queries under reasonable assumptions about the sampling coverage of the
nodes that may issue \(k\)th-hop traceroute queries. In
addition, we introduce a number of new algorithmic techniques, including
a high-probability parametric parallelization of a graph clustering
technique of Thorup and Zwick, which may be of independent interest.