More Web Proxy on the site http://driver.im/

Article

Cache-oblivious planar shortest paths

Authors:

Norbert ZehAuthors Info & Claims

ICALP'05: Proceedings of the 32nd international conference on Automata, Languages and Programming

Pages 563 - 575

https://doi.org/10.1007/11523468_46

Published: 11 July 2005 Publication History

Abstract

We present an efficient cache-oblivious implementation of the shortest-path algorithm for planar graphs by Klein et al., and prove that it incurs no more than ${\mathcal O}(\frac{N}{B^{1/2 - \epsilon}} + \frac{N}{B}{\rm log}N$) block transfers on a graph with N vertices. This is the first cache-oblivious algorithm for this problem that incurs o(N) block transfers.

References

[1]

A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Comm. ACM, pp. 1116-1127, 1988.

Digital Library

[2]

L. Arge, M. A. Bender, E. Demaine, B. Holland-Minkley, and J. I. Munro. Cache-oblivious priority queue and graph algorithm applications. Proc. 34th STOC, pp. 268-276, 2002.

Digital Library

[3]

L. Arge, G. S. Brodal, and L. Toma. On external-memory MST, SSSP and multiway planar graph separation. J. Alg., 53:186-206, 2004.

Digital Library

[4]

L. Arge, U. Meyer, and L. Toma. External memory algorithms for diameter and all-pairs shortest-paths on sparse graphs. Proc. 31st ICALP, LNCS 3142, pp. 146- 157. Springer-Verlag, 2004.

[5]

L. Arge, U. Meyer, L. Toma, and N. Zeh. On external-memory planar depth first search. J. Graph Alg. and Appl., 7(2):105-129, 2003.

Digital Library

[6]

L. Arge and L. Toma. Simplified external memory algorithms for planar DAGs. Proc. 9th SWAT, LNCS 3111, pp. 493-503. Springer-Verlag, 2004.

[7]

L. Arge, L. Toma, and N. Zeh. I/O-efficient algorithms for planar digraphs. Proc. 15th SPAA, pp. 85-93. 2003.

Digital Library

[8]

L. Arge and N. Zeh. I/O-efficient strong connectivity and depth-first search for directed planar graphs. Proc. 44th FOCS, pp. 261-270, 2003.

Digital Library

[9]

G. S. Brodal and R. Fagerberg. Cache oblivious distribution sweeping. Proc. 29th ICALP, LNCS 2380, pp. 426-438. Springer-Verlag, 2002.

Digital Library

[10]

G. S. Brodal and R. Fagerberg. Funnel heap--a cache oblivious priority queue. Proc. 13th ISAAC, LNCS 2518, pp. 219-228. Springer-Verlag, 2002.

Digital Library

[11]

G. S. Brodal and R. Fagerberg. On the limits of cache-obliviousness. Proc. 35th STOC, pp. 307-315, 2003.

Digital Library

[12]

G. S. Brodal, R. Fagerberg, U. Meyer, and N. Zeh. Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths. Proc. 9th SWAT, LNCS 3111, pp. 480-492. Springer-Verlag, 2004.

[13]

Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. Proc. 6th SODA, pp. 139-149, 1995.

Digital Library

[14]

R. A. Chowdhury and V. Ramachandran. Cache-oblivious shortest paths in graphs using buffer heap. Proc. 16th SPAA, pp. 245-254, 2004.

Digital Library

[15]

E. W. Dijkstra. A note on two problems in connection with graphs. Num. Math., 1:269-271, 1959.

Digital Library

[16]

J. Fakcharoenphol and S. Rao. Planar graphs, negative weight edges, shortest paths, near linear time. Proc. 42nd FOCS, pp. 232-241, 2001.

Digital Library

[17]

G. N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comp., 16:1004-1022, 1987.

Digital Library

[18]

M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. Proc. 40th FOCS, pp. 285-297, 1999.

Digital Library

[19]

P. Klein, S. Rao, M. Rauch, and S. Subramanian. Faster shortest path algorithms for planar graphs. J. Comp. Sys. Sci., 55:3-23, 1997.

Digital Library

[20]

A. Maheshwari and N. Zeh. I/O-optimal algorithms for planar graphs using separators. Proc. 13th SODA, pp. 372-381, 2002.

Digital Library

[21]

S. Pettie and V. Ramachandran. Computing shortest paths with comparisons and additions. Proc. 13th SODA, pp. 267-276, 2002.

Digital Library

[22]

M. Thorup. Undirected single source shortest paths with positive integer weights in linear time. J. ACM, 46:362-394, 1999.

Digital Library

[23]

M. Thorup. Floats, integers, and single source shortest paths. J. Alg., 35:189-201, 2000.

Digital Library

Cited By

Hazel TToma LVahrenhold JWickremesinghe R(2008)TerracostACM Journal of Experimental Algorithmics10.1145/1227161.137060012(1-31)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1227161.1370600
Brodal GFagerberg RVinther K(2008)Engineering a cache-oblivious sorting algorithmACM Journal of Experimental Algorithmics10.1145/1227161.122716412(1-23)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1227161.1227164
Allulli LLichodzijewski PZeh NGabow H(2007)A faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge lengthsProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1283383.1283481(910-919)Online publication date: 7-Jan-2007
https://dl.acm.org/doi/10.5555/1283383.1283481

Cache-oblivious planar shortest paths
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Computing almost shortest paths

We study the <i>s-sources almost shortest paths</i> (abbreviated <i>s-ASP</i>) problem. Given an unweighted graph <i>G</i> = (<i>V,E</i>), and a subset <i>S</i> &sube; <i>V</i> of <i>s</i> nodes, the goal is to compute almost shortest paths between ...
Cache-Oblivious Buffer Heap and Cache-Efficient Computation of Shortest Paths in Graphs

We present the buffer heap, a cache-oblivious priority queue that supports Delete-Min, Delete, and a hybrid Insert/Decrease-Key operation in O(1/B log₂ N/M) amortized block transfers from main memory, where M and B are the (unknown) cache size and block ...
Cache-oblivious shortest paths in graphs using buffer heap
SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures

We present the Buffer Heap (BH), a cache-oblivious priority queue that supports Delete-Min, Delete, and Decrease-Key operations in O(1overB log₂ NoverB) amortized block transfers from external memory, where B is the (unknown) block-size and N is the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICALP'05: Proceedings of the 32nd international conference on Automata, Languages and Programming

July 2005

1476 pages

ISBN:3540275800

Editors:
Luís Caires
CITI / Departamento de Informática, Universidade Nova de Lisboa, Portugal
,
Giuseppe F. Italiano
Dipartimento di Informatica, Sistemi e Produzione, Università di Roma "Tor Vergata", via del Politecnico 1, Roma, Italy
,
Luís Monteiro
Departamento de Informatica, Universidade Nova de Lisboa, via del Politecnico 1, Caparica, Portugal
,
Catuscia Palamidessi
Departamento de Informatica, Ecole Polytechnique, Rue de Saclay, Palaiseau Cedex, France
,
Moti Yung
Computer Science Department, Google Inc. and Columbia University, 1214 Amsterdam Avenue, New York, France

Sponsors

Fundacao para a Ciencia e Tecnologia
FCT: Foundation for Science and Technology
Centro de Lógica e Computação/IST/UTL: Centro de Lógica e Computação/IST/UTL

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 11 July 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hazel TToma LVahrenhold JWickremesinghe R(2008)TerracostACM Journal of Experimental Algorithmics10.1145/1227161.137060012(1-31)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1227161.1370600
Brodal GFagerberg RVinther K(2008)Engineering a cache-oblivious sorting algorithmACM Journal of Experimental Algorithmics10.1145/1227161.122716412(1-23)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1227161.1227164
Allulli LLichodzijewski PZeh NGabow H(2007)A faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge lengthsProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1283383.1283481(910-919)Online publication date: 7-Jan-2007
https://dl.acm.org/doi/10.5555/1283383.1283481

View Options

View options

Figures

Tables

Media

View Table of Conten