Aarhus University Seal / Aarhus Universitets segl

Lars Arge

Parallel External Memory Graph Algorithms

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Department of Computer Science
In this paper, we study parallel I/O efficient graph algorithms in the Parallel External Memory (PEM) model, one o f the private-cache chip multiprocessor (CMP) models. We study the fundamental problem of list ranking which leads to efficient solutions to problems on trees, such as computing lowest common ancestors, tree contraction and expression tree evaluation. We also study the problems of computing the connected and biconnected components of a graph, minimum spanning tree of a connected graph and ear decomposition of a biconnected graph. All our solutions on a P-processor PEM model provide an optimal speedup of ¿(P) in parallel I/O complexity and parallel computation time, compared to the single-processor external memory counterparts.
Original languageEnglish
JournalI P D P S Proceedings
Pages (from-to)1-11
Number of pages12
Publication statusPublished - 2010
EventIEEE International Symposium on Parallel & Distributed Processing. IPDPS - Atlanta, GA, United States
Duration: 19 Apr 201023 Apr 2010


ConferenceIEEE International Symposium on Parallel & Distributed Processing. IPDPS
CountryUnited States
CityAtlanta, GA

Bibliographical note

Program chair: Cynthia Phillips
ISBN: 978-1-4244-6442-5

See relations at Aarhus University Citationformats

ID: 22380260