A functional approach to external graph algorithms

James Abello, Adam L. Buchsbaum, Jeffery R. Westbrook

Research output: Chapter in Book/Report/Conference proceedingConference contribution

72 Scopus citations

Abstract

We present a new approach for designing external graph algorithms and use it to design simple external algorithms for computing connected components, minimum spanning trees, bottleneck minimum spanning trees, and maximal matchings in undirected graphs and multi-graphs. Our I/O bounds compete with those of previous approaches. Unlike previous approaches, ours is purely functional-without side effects-and is thus amenable to standard checkpointing and programming language optimization techniques. This is an important practical consideration for applications that may take hours to run.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 1998 - 6th Annual European Symposium, Proceedings
PublisherSpringer Verlag
Pages332-343
Number of pages12
ISBN (Print)3540648488, 9783540648482
DOIs
StatePublished - 1998
Externally publishedYes
Event6th Annual European Symposium on Algorithms, ESA 1998 - Venice, Italy
Duration: Aug 24 1998Aug 26 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1461 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th Annual European Symposium on Algorithms, ESA 1998
Country/TerritoryItaly
CityVenice
Period8/24/988/26/98

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A functional approach to external graph algorithms'. Together they form a unique fingerprint.

Cite this