TY - JOUR

T1 - Geometry, flows, and graph-partitioning algorithms

AU - Arora, Sanjeev

AU - Rao, Satish

AU - Vazirani, Umesh

PY - 2008/10/1

Y1 - 2008/10/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=53349160856&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=53349160856&partnerID=8YFLogxK

U2 - 10.1145/1400181.1400204

DO - 10.1145/1400181.1400204

M3 - Article

AN - SCOPUS:53349160856

SN - 0001-0782

VL - 51

SP - 96

EP - 105

JO - Communications of the ACM

JF - Communications of the ACM

IS - 10

ER -