NDLI: Preprocess, Set, Query!

Content Provider	Springer Nature Link
Author	Porat, Ely Roditty, Liam
Copyright Year	2013
Abstract	Thorup and Zwick (J. ACM 52(1):1–24, 2005 and STOC’01) in their seminal work introduced the notion of distance oracles. Given an n-vertex weighted undirected graph with m edges, they show that for any integer k≥1 it is possible to preprocess the graph in $\tilde {O}(mn^{1/k})$ time and generate a compact data structure of size O(kn 1+1/k ). For each pair of vertices, it is then possible to retrieve an estimated distance with multiplicative stretch 2k−1 in O(k) time. For k=2 this gives an oracle of O(n 1.5) size that produces in constant time estimated distances with stretch 3. Recently, Pǎtraşcu and Roditty (In: Proc. of 51st FOCS, 2010) broke the theoretical status-quo in the field of distance oracles and obtained a distance oracle for sparse unweighted graphs of O(n 5/3) size that produces in constant time estimated distances with stretch 2.In this paper we show that it is possible to break the stretch 2 barrier at the price of non-constant query time in unweighted undirected graphs. We present a data structure that produces estimated distances with 1+ε stretch. The size of the data structure is O(nm 1−ε′) and the query time is $\tilde {O}(m^{1-\varepsilon '})$ . Using it for sparse unweighted graphs we can get a data structure of size O(n 1.87) that can supply in O(n 0.87) time estimated distances with multiplicative stretch 1.75.
Starting Page	516
Ending Page	528
Page Count	13
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	67
Issue Number	4
e-ISSN	14320541
Language	English
Publisher	Springer US
Publisher Date	2013-08-28
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Graph algorithms Distance oracles Data structures Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Compact Navigation and Distance Oracles for Graphs with Small Treewidth

Distance Oracles for Time-Dependent Networks

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision

On Resilient Graph Spanners

On Exact Quantum Query Complexity

Capacitated Domination: Problem Complexity and Approximation Algorithms

On Bounded Leg Shortest Paths Problems

The Parameterized Complexity of Geometric Graph Isomorphism

F-Sensitivity Distance Oracles and Routing Schemes

Preprocess, Set, Query!

Similar Documents

Compact Navigation and Distance Oracles for Graphs with Small Treewidth

Distance Oracles for Time-Dependent Networks

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision

On Resilient Graph Spanners

On Exact Quantum Query Complexity

Capacitated Domination: Problem Complexity and Approximation Algorithms

On Bounded Leg Shortest Paths Problems

The Parameterized Complexity of Geometric Graph Isomorphism

F-Sensitivity Distance Oracles and Routing Schemes

Preprocess, Set, Query!