A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs. / Das, Debarati; Kipouridis, Evangelos; Gutenberg, Maximilian Probst; Wulff-Nilsen, Christian.

Proceedings, Symposium on Simplicity in Algorithms (SOSA). SIAM, 2022. p. 1-11.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Harvard

Das, D, Kipouridis, E, Gutenberg, MP & Wulff-Nilsen, C 2022, A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs. in Proceedings, Symposium on Simplicity in Algorithms (SOSA). SIAM, pp. 1-11, Fifth SIAM Symposium on Simplicity of Algorithms (SOSA 2022) , Virtual, 10/01/2022. https://doi.org/10.1137/1.9781611977066.1

APA

Das, D., Kipouridis, E., Gutenberg, M. P., & Wulff-Nilsen, C. (2022). A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs. In Proceedings, Symposium on Simplicity in Algorithms (SOSA) (pp. 1-11). SIAM. https://doi.org/10.1137/1.9781611977066.1

Vancouver

Das D, Kipouridis E, Gutenberg MP, Wulff-Nilsen C. A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs. In Proceedings, Symposium on Simplicity in Algorithms (SOSA). SIAM. 2022. p. 1-11 https://doi.org/10.1137/1.9781611977066.1

Author

Das, Debarati ; Kipouridis, Evangelos ; Gutenberg, Maximilian Probst ; Wulff-Nilsen, Christian. / A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs. Proceedings, Symposium on Simplicity in Algorithms (SOSA). SIAM, 2022. pp. 1-11

Bibtex

@inproceedings{52e6205a934a42e194c488f14cb7f374,
title = "A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs",
abstract = "Given an n-vertex planar embedded digraph G with non-negative edge weights and a face f of G, Klein presented a data structure with O(nlogn) space and preprocessing time which can answer any query (u,v) for the shortest path distance in G from u to v or from v to u in O(logn) time, provided u is on f. This data structure is a key tool in a number of state-of-the-art algorithms and data structures for planar graphs.Klein's data structure relies on dynamic trees and the persistence technique as well as a highly non-trivial interaction between primal shortest path trees and their duals. The construction of our data structure follows a completely different and in our opinion very simple divide-and-conquer approach that solely relies on Single-Source Shortest Path computations and contractions in the primal graph. Our space and preprocessing time bound is O(nlog|f|) and query time is O(log|f|) which is an improvement over Klein's data structure when f has small size. ",
author = "Debarati Das and Evangelos Kipouridis and Gutenberg, {Maximilian Probst} and Christian Wulff-Nilsen",
year = "2022",
doi = "10.1137/1.9781611977066.1",
language = "English",
pages = "1--11",
booktitle = "Proceedings, Symposium on Simplicity in Algorithms (SOSA)",
publisher = "SIAM",
note = "Fifth SIAM Symposium on Simplicity of Algorithms (SOSA 2022) ; Conference date: 10-01-2022 Through 11-01-2022",

}

RIS

TY - GEN

T1 - A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs

AU - Das, Debarati

AU - Kipouridis, Evangelos

AU - Gutenberg, Maximilian Probst

AU - Wulff-Nilsen, Christian

PY - 2022

Y1 - 2022

N2 - Given an n-vertex planar embedded digraph G with non-negative edge weights and a face f of G, Klein presented a data structure with O(nlogn) space and preprocessing time which can answer any query (u,v) for the shortest path distance in G from u to v or from v to u in O(logn) time, provided u is on f. This data structure is a key tool in a number of state-of-the-art algorithms and data structures for planar graphs.Klein's data structure relies on dynamic trees and the persistence technique as well as a highly non-trivial interaction between primal shortest path trees and their duals. The construction of our data structure follows a completely different and in our opinion very simple divide-and-conquer approach that solely relies on Single-Source Shortest Path computations and contractions in the primal graph. Our space and preprocessing time bound is O(nlog|f|) and query time is O(log|f|) which is an improvement over Klein's data structure when f has small size.

AB - Given an n-vertex planar embedded digraph G with non-negative edge weights and a face f of G, Klein presented a data structure with O(nlogn) space and preprocessing time which can answer any query (u,v) for the shortest path distance in G from u to v or from v to u in O(logn) time, provided u is on f. This data structure is a key tool in a number of state-of-the-art algorithms and data structures for planar graphs.Klein's data structure relies on dynamic trees and the persistence technique as well as a highly non-trivial interaction between primal shortest path trees and their duals. The construction of our data structure follows a completely different and in our opinion very simple divide-and-conquer approach that solely relies on Single-Source Shortest Path computations and contractions in the primal graph. Our space and preprocessing time bound is O(nlog|f|) and query time is O(log|f|) which is an improvement over Klein's data structure when f has small size.

U2 - 10.1137/1.9781611977066.1

DO - 10.1137/1.9781611977066.1

M3 - Article in proceedings

SP - 1

EP - 11

BT - Proceedings, Symposium on Simplicity in Algorithms (SOSA)

PB - SIAM

T2 - Fifth SIAM Symposium on Simplicity of Algorithms (SOSA 2022)

Y2 - 10 January 2022 through 11 January 2022

ER -

ID: 300443460