Fast and Compact Exact Distance Oracle for Planar Grap

Vincent Pierre Cohen-Addad; Søren Dahlgaard; Christian Wulff-Nilsen

doi:10.1109/FOCS.2017.93

Fast and Compact Exact Distance Oracle for Planar Grap

Vincent Pierre Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen

Datalogisk Institut

18 Citationer (Scopus)

Abstract

For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an O(n 5/3)-space distance oracle which answers exact distance queries in O(log n) time for n-vertex planar edge-weighted digraphs. All previous distance oracles for planar graphs with truly subquadratic space (i.e., space O(n 2- ) for some constant 0) either required query time polynomial in n or could only answer approximate distance queries.Furthermore, we show how to trade-off time and space: For any S ϵ n 3/2, we show how to obtain an S-space distance 5/2 oracle that answers queries in time O(S n 3/2 log n). This is a polynomial improvement over the previous planar distance oracles with o(n 1/4) query time.

Originalsprog	Engelsk
Titel	2017 IEEE 58th Annual IEEE Symposium on Foundations of Computer Science (FOcS)
Forlag	IEEE
Publikationsdato	10 nov. 2017
Sider	962-973
DOI	https://doi.org/10.1109/FOCS.2017.93
Status	Udgivet - 10 nov. 2017
Begivenhed	58th Annual IEEE Symposium on Foundations of Computer Science - Berkeley, USA Varighed: 15 okt. 2017 → 17 okt. 2017 Konferencens nummer: 58

Konference

Konference	58th Annual IEEE Symposium on Foundations of Computer Science
Nummer	58
Land/Område	USA
By	Berkeley
Periode	15/10/2017 → 17/10/2017

Adgang til dokumentet

10.1109/FOCS.2017.93

Citationsformater

@inproceedings{fdccdccd9081465a8ef4007e4c6c6468,

title = "Fast and Compact Exact Distance Oracle for Planar Grap",

abstract = "For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an O(n 5/3)-space distance oracle which answers exact distance queries in O(log n) time for n-vertex planar edge-weighted digraphs. All previous distance oracles for planar graphs with truly subquadratic space (i.e., space O(n 2- ) for some constant 0) either required query time polynomial in n or could only answer approximate distance queries.Furthermore, we show how to trade-off time and space: For any S ϵ n 3/2, we show how to obtain an S-space distance 5/2 oracle that answers queries in time O(S n 3/2 log n). This is a polynomial improvement over the previous planar distance oracles with o(n 1/4) query time.",

keywords = "dynamic graph algorithms, minimum spanning forests, graph decomposition",

author = "Cohen-Addad, {Vincent Pierre} and S{\o}ren Dahlgaard and Christian Wulff-Nilsen",

year = "2017",

month = nov,

day = "10",

doi = "10.1109/FOCS.2017.93",

language = "English",

pages = "962--973",

booktitle = "2017 IEEE 58th Annual IEEE Symposium on Foundations of Computer Science (FOcS)",

publisher = "IEEE",

note = "58th Annual IEEE Symposium on Foundations of Computer Science ; Conference date: 15-10-2017 Through 17-10-2017",

}

TY - GEN

T1 - Fast and Compact Exact Distance Oracle for Planar Grap

AU - Cohen-Addad, Vincent Pierre

AU - Dahlgaard, Søren

AU - Wulff-Nilsen, Christian

N1 - Conference code: 58

PY - 2017/11/10

Y1 - 2017/11/10

N2 - For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an O(n 5/3)-space distance oracle which answers exact distance queries in O(log n) time for n-vertex planar edge-weighted digraphs. All previous distance oracles for planar graphs with truly subquadratic space (i.e., space O(n 2- ) for some constant 0) either required query time polynomial in n or could only answer approximate distance queries.Furthermore, we show how to trade-off time and space: For any S ϵ n 3/2, we show how to obtain an S-space distance 5/2 oracle that answers queries in time O(S n 3/2 log n). This is a polynomial improvement over the previous planar distance oracles with o(n 1/4) query time.

AB - For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an O(n 5/3)-space distance oracle which answers exact distance queries in O(log n) time for n-vertex planar edge-weighted digraphs. All previous distance oracles for planar graphs with truly subquadratic space (i.e., space O(n 2- ) for some constant 0) either required query time polynomial in n or could only answer approximate distance queries.Furthermore, we show how to trade-off time and space: For any S ϵ n 3/2, we show how to obtain an S-space distance 5/2 oracle that answers queries in time O(S n 3/2 log n). This is a polynomial improvement over the previous planar distance oracles with o(n 1/4) query time.

KW - dynamic graph algorithms

KW - minimum spanning forests

KW - graph decomposition

U2 - 10.1109/FOCS.2017.93

DO - 10.1109/FOCS.2017.93

M3 - Article in proceedings

SP - 962

EP - 973

BT - 2017 IEEE 58th Annual IEEE Symposium on Foundations of Computer Science (FOcS)

PB - IEEE

T2 - 58th Annual IEEE Symposium on Foundations of Computer Science

Y2 - 15 October 2017 through 17 October 2017

ER -

Fast and Compact Exact Distance Oracle for Planar Grap

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater