Planar reachability in linear space and constant time

Jacob Holm; Eva Rotenberg; Mikkel Thorup

doi:10.1109/FOCS.2015.30

Planar reachability in linear space and constant time

Jacob Holm, Eva Rotenberg, Mikkel Thorup

Datalogisk Institut

6 Citationer (Scopus)

Abstract

We show how to represent a planar digraph in linear space so that reach ability queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reach ability is thus optimal in both time and space, and has optimal construction time. The previous best solution used O(n log n) space for constant query time [Thorup FOCS'01].

Originalsprog	Engelsk
Titel	2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)
Antal sider	20
Forlag	IEEE
Publikationsdato	11 dec. 2015
Sider	370-389
DOI	https://doi.org/10.1109/FOCS.2015.30
Status	Udgivet - 11 dec. 2015
Begivenhed	The Annual Symposium on Foundations of Computer Science - DoubleTree Hotel, Berkeley, California, USA Varighed: 18 okt. 2015 → 20 okt. 2015 Konferencens nummer: 56

Konference

Konference	The Annual Symposium on Foundations of Computer Science
Nummer	56
Lokation	DoubleTree Hotel
Land/Område	USA
By	Berkeley, California
Periode	18/10/2015 → 20/10/2015

Navn	Symposium on Foundations of Computer Science. Annual Proceedings
ISSN	1523-8288

Adgang til dokumentet

10.1109/FOCS.2015.30

Planar Reachability in Linear Space and Constant TimeForlagets udgivne version, 398 KB

http://arxiv.org/pdf/1411.5867v2.pdfLicens: Andet

Citationsformater

Planar reachability in linear space and constant time. / Holm, Jacob; Rotenberg, Eva; Thorup, Mikkel.
2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2015. s. 370-389 (Symposium on Foundations of Computer Science. Annual Proceedings).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Holm, J, Rotenberg, E & Thorup, M 2015, Planar reachability in linear space and constant time. i 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, Symposium on Foundations of Computer Science. Annual Proceedings, s. 370-389, The Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, 18/10/2015. https://doi.org/10.1109/FOCS.2015.30

@inproceedings{a13cb0cbb19a4d0c877989a883b72c0f,

title = "Planar reachability in linear space and constant time",

abstract = "We show how to represent a planar digraph in linear space so that reach ability queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reach ability is thus optimal in both time and space, and has optimal construction time. The previous best solution used O(n log n) space for constant query time [Thorup FOCS'01].",

author = "Jacob Holm and Eva Rotenberg and Mikkel Thorup",

year = "2015",

month = dec,

day = "11",

doi = "10.1109/FOCS.2015.30",

language = "English",

series = "Symposium on Foundations of Computer Science. Annual Proceedings",

publisher = "IEEE",

pages = "370--389",

booktitle = "2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)",

note = "The Annual Symposium on Foundations of Computer Science ; Conference date: 18-10-2015 Through 20-10-2015",

}

TY - GEN

T1 - Planar reachability in linear space and constant time

AU - Holm, Jacob

AU - Rotenberg, Eva

AU - Thorup, Mikkel

N1 - Conference code: 56

PY - 2015/12/11

Y1 - 2015/12/11

N2 - We show how to represent a planar digraph in linear space so that reach ability queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reach ability is thus optimal in both time and space, and has optimal construction time. The previous best solution used O(n log n) space for constant query time [Thorup FOCS'01].

AB - We show how to represent a planar digraph in linear space so that reach ability queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reach ability is thus optimal in both time and space, and has optimal construction time. The previous best solution used O(n log n) space for constant query time [Thorup FOCS'01].

U2 - 10.1109/FOCS.2015.30

DO - 10.1109/FOCS.2015.30

M3 - Article in proceedings

T3 - Symposium on Foundations of Computer Science. Annual Proceedings

SP - 370

EP - 389

BT - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)

PB - IEEE

T2 - The Annual Symposium on Foundations of Computer Science

Y2 - 18 October 2015 through 20 October 2015

ER -

Planar reachability in linear space and constant time

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater