Name
Abstract | ||
|---|---|---|
We present a versatile and scalable algorithm for computing exact distances on real-world networks with tens of millions of arcs in real time. Unlike existing approaches, preprocessing and queries are practical on a wide variety of inputs, such as social, communication, sensor, and road networks. We achieve this by providing a unified approach based on the concept of 2-hop labels, improving upon existing methods. In particular, we introduce a fast sampling-based algorithm to order vertices by importance, as well as effective compression techniques. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-662-44777-2_27 | ALGORITHMS - ESA 2014 |
Field | DocType | Volume |
Discrete mathematics,Road networks,Vertex (geometry),Computer science,Theoretical computer science,Betweenness centrality,Preprocessor,Scalable algorithms,Sampling (statistics) | Conference | 8737 |
ISSN | Citations | PageRank |
0302-9743 | 22 | 0.84 |
References | Authors | |
20 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Delling | 1 | 2049 | 108.90 |
| Andrew V. Goldberg | 2 | 5883 | 676.30 |
| Thomas Pajor | 3 | 397 | 22.39 |
| Renato F. Werneck | 4 | 1743 | 84.33 |