TY - GEN
T1 - Graph partitioning for dynamic, adaptive and multi-phase computations
AU - Kumar, Vipin
PY - 2000/1/1
Y1 - 2000/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84959016959&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84959016959&partnerID=8YFLogxK
U2 - 10.1007/3-540-45591-4_63
DO - 10.1007/3-540-45591-4_63
M3 - Conference contribution
AN - SCOPUS:84959016959
SN - 354067442X
SN - 354067442X
SN - 9783540674429
SN - 9783540674429
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
BT - Parallel and Distributed Processing - 15 IPDPS 2000 Workshops, Proceedings
A2 - Rolim, Jose
PB - Springer- Verlag
T2 - IEEE International Parallel and Distributed Processing Symposium, IPDPS 2000
Y2 - 1 May 2000 through 5 May 2000
ER -