Document Open Access Logo

Space-efficient Basic Graph Algorithms

Authors Amr Elmasry, Torben Hagerup, Frank Kammer

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2015.288.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • graph algorithms
  • depth-first search
  • single-source shortest paths
  • register input model

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We reconsider basic algorithmic graph problems in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O(n) bits or little more than that. For computing connected components and performing breadth-first search, we match
the running times of standard algorithms that have no memory restrictions, for depth-first search and related problems we come within a factor of \Theta(\log\log n), and for computing minimum spanning forests and single-source shortest-paths trees we come close for sparse input graphs.

Cite As Get BibTex

Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient Basic Graph Algorithms. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 288-301, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.288

Author Details

Amr Elmasry
Torben Hagerup
Frank Kammer

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983. Google Scholar
  2. Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, and André Schulz. Reprint of: Memory-constrained algorithms for simple polygons. Comput. Geom. Theory Appl., 47(3, Part B):469-479, 2014. Google Scholar
  3. Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, and Ryuhei Uehara. Depth-first search using O(n) bits. In Proc. 25th International Symposium on Algorithms and Computation (ISAAC 2014), volume 8889 of LNCS, pages 553-564. Springer, 2014. Google Scholar
  4. Tetsuo Asano, Wolfgang Mulzer, Günter Rote, and Yajun Wang. Constant-work-space algorithms for geometric problems. J. Comput. Geom., 2(1):46-68, 2011. Google Scholar
  5. Luis Barba, Matias Korman, Stefan Langerman, and Rodrigo I. Silveira. Computing a visibility polygon using few variables. Comput. Geom. Theory Appl., 47(9):918-926, 2014. Google Scholar
  6. Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira, and Kunihiko Sadakane. Space-time trade-offs for stack-based algorithms. In Proc. 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20 of LIPIcs, pages 281-292. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. Google Scholar
  7. Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM J. Comput., 27(5):1273-1282, 1998. Google Scholar
  8. Paul Beame. A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput., 20(2):270-277, 1991. Google Scholar
  9. Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, and Godfried Toussaint. Space-efficient planar convex hull algorithms. Theor. Comput. Sci., 321(1):25-40, 2004. Google Scholar
  10. Timothy M. Chan. Comparison-based time-space lower bounds for selection. ACM Trans. Algorithms, 6(2):Article 26, 2010. Google Scholar
  11. Timothy M. Chan and Eric Y. Chen. Multi-pass geometric algorithms. Discrete Comput. Geom., 37(1):79-102, 2007. Google Scholar
  12. Timothy M. Chan, J. Ian Munro, and Venkatesh Raman. Faster, space-efficient selection algorithms in read-only memory for integers. In Proc. 24th International Symposium on Algorithms and Computation (ISAAC 2013), volume 8283 of LNCS, pages 405-412. Springer, 2013. Google Scholar
  13. Timothy M. Chan, J. Ian Munro, and Venkatesh Raman. Selection and sorting in the "restore" model. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pages 995-1004. SIAM, 2014. Google Scholar
  14. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009. Google Scholar
  15. George B. Dantzig. On the shortest route through a network. Manag. Sci., 6(2):187-190, 1960. Google Scholar
  16. Omar Darwish and Amr Elmasry. Optimal time-space tradeoff for the 2D convex-hull problem. In Proc. 22nd Annual European Symposium on Algorithms (ESA 2014), volume 8737 of LNCS, pages 284-295. Springer, 2014. Google Scholar
  17. Bireswar Das, Samir Datta, and Prajakta Nimbhorkar. Log-space algorithms for paths and matchings in k-trees. Theory Comput. Syst., 53(4):669-689, 2013. Google Scholar
  18. Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted space algorithms for isomorphism on bounded treewidth graphs. Inform. Comput., 217:71-83, 2012. Google Scholar
  19. E. W. Dijkstra. A note on two problems in connexion with graphs. Numer. Math., 1(1):269-271, 1959. Google Scholar
  20. Jeff Edmonds, Chung Keung Poon, and Dimitris Achlioptas. Tight lower bounds for st-connectivity on the NNJAG model. SIAM J. Comput., 28(6):2257-2284, 1999. Google Scholar
  21. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pages 143-152. IEEE Computer Society, 2010. Google Scholar
  22. Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In Proc. 46th ACM Symposium on Theory of Computing (STOC 2014), pages 383-392. ACM, 2014. Google Scholar
  23. Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, and Srinivasa Rao Satti. Selection from read-only memory with limited workspace. Theor. Comput. Sci., 554:64-73, 2014. Google Scholar
  24. Greg N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. J. Comput. Syst. Sci., 34(1):19-26, 1987. Google Scholar
  25. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. Google Scholar
  26. Torben Hagerup and Frank Kammer. Dynamic data structures for the succinct RAM, 2015. In preparation. Google Scholar
  27. J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. Theor. Comput. Sci., 12(3):315-323, 1980. Google Scholar
  28. J. Ian Munro and Venkatesh Raman. Selection from read-only memory and sorting with minimum data movement. Theor. Comput. Sci., 165(2):311-323, 1996. Google Scholar
  29. Jakob Pagter and Theis Rauhe. Optimal time-space trade-offs for sorting. In Proc. 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1998), pages 264-268. IEEE Computer Society, 1998. Google Scholar
  30. R. C. Prim. Shortest connection networks and some generalizations. Bell Syst. Tech. J., 36(6):1389-1401, 1957. Google Scholar
  31. Venkatesh Raman and Sarnath Ramnath. Improved upper bounds for time-space trade-offs for selection. Nord. J. Comput., 6(2):162-180, 1999. Google Scholar
  32. Robert Tarjan. Finding dominators in directed graphs. SIAM J. Comput., 3(1):62-89, 1974. Google Scholar
  33. Martin Tompa. Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations. SIAM J. Comput., 11(1):130-137, 1982. Google Scholar
  34. P. D. Whiting and J. A. Hillier. A method for finding the shortest route through a road network. J. Oper. Res. Soc., 11(1/2):37-40, 1960. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact