Treffer: Geometry, Flows, and Graph-Partitioning Algorithms.

Title:
Geometry, Flows, and Graph-Partitioning Algorithms.
Authors:
Arora, Sanjeev1 arora@cs.princeton.edu, Rao, Satish2 satishr@cs.berkeley.edu, Vazirani, Umesh2 vazirani@cs.berkeley.edu
Source:
Communications of the ACM. Oct2008, Vol. 51 Issue 10, p96-105. 10p. 4 Diagrams, 3 Charts.
Subject Terms:
*Computer science, *Approximation theory, *Computer programming, *Heuristic programming, Integrated circuit design, Algorithm research, Parallel computers, High performance processors, Euclidean algorithm, Embeddings (Mathematics), Geometrical constructions, Spectral geometry
Database:
Business Source Elite

Weitere Informationen

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.