Geometry, flows, and graph-partitioning algorithms

Sanjeev Arora, Satish Rao, Umesh Vazirani

Research output: Contribution to journalArticle

27 Scopus citations

Abstract

Graph partitioning is a computational problems to divide the vertices of a graph into two large pieces with minimum number of the edges. The application of partitioning can be used for computer vision, data analysis, image segmentation, and image analysis. The geometric approach of partitioning start with drawing the graph in a geometric space by keeping small distance between its endpoint and points are spread out. The graph need to draw in a way that the sum of squares of the length of the edges is small and square of the distance between the average pair of points is a fixed constant. Geometric approach can determine how much distortion is require to map the metric space into a Euclidean metric space. Flow based approach also can be used for graph partitioning and designing fast algorithms.

Original languageEnglish (US)
Pages (from-to)96-105
Number of pages10
JournalCommunications of the ACM
Volume51
Issue number10
DOIs
StatePublished - Oct 1 2008

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Geometry, flows, and graph-partitioning algorithms'. Together they form a unique fingerprint.

  • Cite this