Distance labeling in graphs
By C. Gavoille, David Peleg, S. Pérennes, R. Raz. ACM-SIAM Symposium on Discrete Algorithms, 2001
372 citations recorded by the source corpus.
Subfields: Computational Theory and Mathematics
View Paper: https://www.semanticscholar.org/paper/f25a0051d815e78c8c2e2762e49c8b4ce07f0ac0
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Peter Sanders
- Daniel Delling
- Dorothea Wagner
- Haim Kaplan
- Andrew Vladislav Goldberg
- Renato F. Werneck
- Mikkel Thorup
- Uri Zwick
Citations in the corpus
- Route Planning in Transportation Networks (2015, background): “A natural special case of this approach is Hub Labeling (HL) [64,135], in which the label L(u) associated with vertex u consists of a set of vertices (the hubs of u), together with their distances from u.”
- Reachability and distance queries via 2-hop labels (2002, background): “One such example is the family of directed planar graphs: Reachability or (1 +e)-approximate shortest paths have worst-case 2-hop labels of size O(nlog2n) (using some slight modification of a construction by Thorup [ l i D whereas for exact-distances, there is a known ~(n 413) lower-bound for any la”
- A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks (2011, background): “In particular, [15] gives upper and lower bounds on label sizes for general graphs, trees, planar graphs, and bounded degree graphs.”
- Compact oracles for reachability and approximate distances in planar digraphs (2001, positive): “[7] have recently shown that for undirected unweighted graphs, exact distances require a label size of ( 3 p n) bits, and for undirected weighted graphs, the labels require ( p n) bits.”
- Fast construction of nets in low dimensional metrics, and their applications (2004, background): “In [ GPPR04 ] there is a family of n-vertex weighted rooted binary trees, such that any exact distance labeling scheme of the leaves requires labels of length (log bits, where the edge weight is in the range{0,...,M 1}. A further property of that family of trees is that the depth h = M log2n (i.e., ”