Cover Image
QR Code

Geometry, Flows, and Graph-Partitioning Algorithms.

The article discusses graph partitioning within the computing industry, presenting a survey of articles and research on the topic. Graph partitioning concerns itself with vertices of a graph that need to be partitioned into two or more large pieces while at the same time minimizing the number of edg...

Full description

Published in:Communications of the ACM Vol. 51; no. 10; pp. 96 - 106
Main Authors: Arora, Sanjeev, Rao, Satish, Vazirani, Umesh
Format: Article
Published: Association for Computing Machinery Oct2008
Subjects:
Integrated circuit design
Algorithm research
Computer science
Approximation theory
Parallel computers
Computer programming
Online Access:View this record in EBSCOhost
Summary:The article discusses graph partitioning within the computing industry, presenting a survey of articles and research on the topic. Graph partitioning concerns itself with vertices of a graph that need to be partitioned into two or more large pieces while at the same time minimizing the number of edges that cross the cut. Topics include the use of divide and cut algorithms, laying out large circuits on silicon chips, and computation distribution among processors. Also discussed is the design of algorithms with the best provable approximation guarantees.