Graph partitioning for dynamic, adaptive and multi-phase computations

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


Algorithms that find good partitionings of highly unstructured graphs are critical in developing efficient algorithms for problems in a variety of domains such as scientific simulations that require solution to large sparse linear systems, VLSI design, and data mining. Even though this problem is NP-hard, efficient multi-level algorithms have been developed that can find good partitionings of static irregular meshes. The problem of graph partitioning becomes a lot more challenging when the graph is dynamically evolving (e.g., in adaptive computations), or if computation in multiple phases needs to be balanced simultaneously. This talk will discuss these challenges, and then describe some of our recent research in addressing them.

Original languageEnglish (US)
Title of host publicationParallel and Distributed Processing - 15 IPDPS 2000 Workshops, Proceedings
EditorsJose Rolim
PublisherSpringer Verlag
Number of pages1
ISBN (Print)354067442X, 354067442X, 9783540674429, 9783540674429
StatePublished - 2000
EventIEEE International Parallel and Distributed Processing Symposium, IPDPS 2000 - Cancun, Mexico
Duration: May 1 2000May 5 2000

Publication series

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


OtherIEEE International Parallel and Distributed Processing Symposium, IPDPS 2000

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.


Dive into the research topics of 'Graph partitioning for dynamic, adaptive and multi-phase computations'. Together they form a unique fingerprint.

Cite this