English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Approximate distance oracle for unweighted graphs in Õ(n²) time

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.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Baswana, Surender1, Author           
Sen, Sandeep1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2005-06-282004
 Publication Status: Issued
 Pages: -
 Publishing info: New York, USA : ACM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 232066
Other: Local-ID: C1256428004B93B8-972E885DC480DA3CC1256E8A0056DBC6-BS2004
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: New Orleans, USA
Start-/End Date: 2004-01-11

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: New York, USA : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 271 - 280 Identifier: ISBN: 0-89871-XXX-X