Imagen de Portada
Código QR

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

Descripción completa

Publicado en:Communications of the ACM Vol. 51; no. 10; pp. 96 - 106
Autores principales: Arora, Sanjeev, Rao, Satish, Vazirani, Umesh
Formato: Artículo
Publicado: Association for Computing Machinery Oct2008
Materias:
Integrated circuit design
Algorithm research
Computer science
Approximation theory
Parallel computers
Computer programming
Acceso en línea:Ver este registro en EBSCOhost
Sumario: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.