Approximate distance oracles for graphs with dense clusters

2017-03-012017-03-012004Andersson, M., Gudmundsson, J. y Levcopoulos, C. (2004). Approximate distance oracles for graphs with dense clusters. En 20th European Workshop on Computational Geometry, Sevilla.http://hdl.handle.net/11441/55008Let 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.application/pdfengAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/Approximate distance oracles for graphs with dense clustersinfo:eu-repo/semantics/conferenceObjectinfo:eu-repo/semantics/openAccess