Graph partitioning for dynamic, adaptive and multi-phase computations

Vipin Kumar

doi:10.1007/3-540-45591-4_63

Graph partitioning for dynamic, adaptive and multi-phase computations

Vipin Kumar

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English (US)
Title of host publication	Parallel and Distributed Processing - 15 IPDPS 2000 Workshops, Proceedings
Editors	Jose Rolim
Publisher	Springer Verlag
Pages	476
Number of pages	1
ISBN (Print)	354067442X, 354067442X, 9783540674429, 9783540674429
DOIs	https://doi.org/10.1007/3-540-45591-4_63
State	Published - 2000
Event	IEEE International Parallel and Distributed Processing Symposium, IPDPS 2000 - Cancun, Mexico Duration: May 1 2000 → May 5 2000

Publication series

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

Other

Other	IEEE International Parallel and Distributed Processing Symposium, IPDPS 2000
Country/Territory	Mexico
City	Cancun
Period	5/1/00 → 5/5/00

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.

Publisher link

10.1007/3-540-45591-4_63

Find It

Find It at U of M Libraries

Cite this

Kumar, V. (2000). Graph partitioning for dynamic, adaptive and multi-phase computations. In J. Rolim (Ed.), Parallel and Distributed Processing - 15 IPDPS 2000 Workshops, Proceedings (pp. 476). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1800). Springer Verlag. https://doi.org/10.1007/3-540-45591-4_63

Graph partitioning for dynamic, adaptive and multi-phase computations. / Kumar, Vipin.
Parallel and Distributed Processing - 15 IPDPS 2000 Workshops, Proceedings. ed. / Jose Rolim. Springer Verlag, 2000. p. 476 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1800).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kumar, V 2000, Graph partitioning for dynamic, adaptive and multi-phase computations. in J Rolim (ed.), Parallel and Distributed Processing - 15 IPDPS 2000 Workshops, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1800, Springer Verlag, pp. 476, IEEE International Parallel and Distributed Processing Symposium, IPDPS 2000, Cancun, Mexico, 5/1/00. https://doi.org/10.1007/3-540-45591-4_63

Kumar V. Graph partitioning for dynamic, adaptive and multi-phase computations. In Rolim J, editor, Parallel and Distributed Processing - 15 IPDPS 2000 Workshops, Proceedings. Springer Verlag. 2000. p. 476. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45591-4_63

@inproceedings{f396f1e3a1a44393bbedfd5f71e7eec7,

title = "Graph partitioning for dynamic, adaptive and multi-phase computations",

abstract = "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.",

author = "Vipin Kumar",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; IEEE International Parallel and Distributed Processing Symposium, IPDPS 2000 ; Conference date: 01-05-2000 Through 05-05-2000",

year = "2000",

doi = "10.1007/3-540-45591-4\_63",

language = "English (US)",

isbn = "354067442X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "476",

editor = "Jose Rolim",

booktitle = "Parallel and Distributed Processing - 15 IPDPS 2000 Workshops, Proceedings",

}

TY - GEN

T1 - Graph partitioning for dynamic, adaptive and multi-phase computations

AU - Kumar, Vipin

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

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 - https://www.scopus.com/pages/publications/84959016959

UR - https://www.scopus.com/pages/publications/84959016959#tab=citedBy

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 - 9783540674429

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 476

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 -

Graph partitioning for dynamic, adaptive and multi-phase computations

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this