Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

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

MPG-Autoren
/persons/resource/persons44080

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

/persons/resource/persons45456

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

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe 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: https://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.