Ponencia
Approximate distance oracles for graphs with dense clusters
Autor/es | Andersson, Mattias
Gudmundsson, Joachim Levcopoulos, Christos |
Fecha de publicación | 2004 |
Fecha de depósito | 2017-03-01 |
Publicado en |
|
Resumen | Let G be a graph containing N disjoint t-spanners that are inter-connected with M edges. We present an algorithm that constructs a data structure of size O(M2 + n log n) that answers (1 + ε)-approximate shortest path queries ... Let G be a graph containing N disjoint t-spanners that are inter-connected with M edges. We present an algorithm that constructs a data structure of size O(M2 + n log n) that answers (1 + ε)-approximate shortest path queries in G in constant time, where n is the number of vertices of G. |
Cita | Andersson, M., Gudmundsson, J. y Levcopoulos, C. (2004). Approximate distance oracles for graphs with dense clusters. En 20th European Workshop on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Approximate distance oracles for ... | 134.1Kb | [PDF] | Ver/ | |