Repositorio de producción científica de la Universidad de Sevilla

Approximate distance oracles for graphs with dense clusters

 

Advanced Search
 
Opened Access Approximate distance oracles for graphs with dense clusters
Cites
Show item statistics
Icon
Export to
Author: Andersson, Mattias
Gudmundsson, Joachim
Levcopoulos, Christos
Date: 2004
Document type: Presentation
Abstract: 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.
Size: 134.1Kb
Format: PDF

URI: http://hdl.handle.net/11441/55008

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)