de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Approximate distance oracle for unweighted graphs in Õ(n²) time

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44080

Baswana,  Surender
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45456

Sen,  Sandeep
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Baswana, S., & Sen, S. (2004). Approximate distance oracle for unweighted graphs in Õ(n²) time. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04) (pp. 271-280). New York, USA: ACM.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-2A2E-9
Zusammenfassung
Let G(V, E) be an undirected weighted graph with |V| = n, |E| = m. Recently Thorup and Zwick introduced a remarkable data-structure that stores all pairs approximate distance information implicitly in o(n2) space, and yet answers any approximate distance query in constant time. They named this data-structure approximate distance oracle because of this feature. Given an integer k < 1, a (2k-1)-approximate distance oracle requires O(kn1+1/k) space and answers a (2k-1)-approximate distance query in O(k) time. Thorup and Zwick showed that a (2k - 1)-approximate distance oracle can be computed in O(kmn1/k) time, and posed the following question : Can (2k - 1)-approximate distance oracle be computed in Õ(n2) time? In this paper, we answer their question in affirmative for unweighted graphs. We present an algorithm that computes (2k -1)-approximate distance oracle for a given unweighted graph in Õ(n2) time. One of the new ideas used in the improved algorithm also leads to the first linear time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph.