Treffer: Space-efficient Basic Graph Algorithms
Title:
Space-efficient Basic Graph Algorithms
Authors:
Contributors:
Amr Elmasry and Torben Hagerup and Frank Kammer
Publisher Information:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Publication Year:
2015
Collection:
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics )
Subject Terms:
Document Type:
Fachzeitschrift
article in journal/newspaper<br />conference object
File Description:
application/pdf
Language:
English
Relation:
Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.288
DOI:
10.4230/LIPIcs.STACS.2015.288
Availability:
Accession Number:
edsbas.AE614BC7
Database:
BASE
Weitere Informationen
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.