Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2019) |
last year
(2018) |
two years ago
(2017) |
Notes URL
Action:
login to update
Options:
Goto entry point
Author, Editor
Author(s):
Meyer, Ulrich
dblp
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
URL of the conference:
http://www.siam.org/meetings/da01/
URL for downloading the paper:
Event Address*:
Washington, DC
Language:
English
Event Date*
(no longer used):
January, 07-09
Organization:
ACM-SIAM
Event Start Date:
22 September 2019
Event End Date:
22 September 2019
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
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