MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Meyer, Ulrichdblp
Editor(s):
BibTeX cite key*:
Meyer2001a
Title, Booktitle
Title*:
External Memory BFS on Undirected Graphs with Bounded Degree
Booktitle*:
Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da01/
Downloading URL:
Event Address*:
Washington, DC
Language:
English
Event Date*
(no longer used):
January, 07-09
Organization:
ACM-SIAM
Event Start Date:
20 January 2021
Event End Date:
20 January 2021
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
87-88
Year*:
2001
VG Wort Pages:
6
ISBN/ISSN:
0-89871-490-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We give the first external memory algorithm for breadth-first search (BFS)
which achieves $o(n)$ I/Os on arbitrary undirected graphs with
$n$ nodes and maximum node degree $d$. Let $M$ and $B>d$ denote
the main memory size and block size, respectively. Using
$\mathrm{Sort}(x)=\Theta(\frac{x}{B}\cdot \log_{M/B}\frac{x}{B})$,
our algorithm needs ${\cal O}(\frac{n}{\gamma \cdot \log_d B}
+ \mathrm{Sort}(n \cdot B^\gamma))$ I/Os and
${\cal O}(n \cdot B^\gamma)$ external space
for an arbitrary parameter $0 <\gamma \le 1/2$.
The result carries over to BFS, depth-first search (DFS) and single
source shortest paths (SSSP) on undirected planar graphs with
arbitrary node degrees.
Keywords:
External Memory Algorithms, Graph Theory
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Meyer2001a,
AUTHOR = {Meyer, Ulrich},
 TITLE = {External Memory BFS on Undirected Graphs with Bounded Degree},
 BOOKTITLE = {Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01)},
 PUBLISHER = {ACM},
 YEAR = {2001},
 ORGANIZATION = {ACM-SIAM},
 PAGES = {87--88},
 ADDRESS = {Washington, DC},
 MONTH = {January},
 ISBN = {0-89871-490-7},
}

Entry last modified by Anja Becker, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ulrich Meyer		Created
01/23/2001 03:25:22 PM
Revisions
8.
7.
6.
5.
4.		Editor(s)
Anja Becker
Anja Becker
Ulrich Meyer
Ulrich Meyer
Ulrich Meyer		Edit Dates
22.03.2002 13:25:24
22.03.2002 13:16:04
08/01/2002 11:40:34
08/01/2002 11:14:28
13/08/2001 13:57:36