Fast approximate graph partitioning algorithms

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber

Research output: Contribution to conferencePaperpeer-review

26 Scopus citations

Abstract

Graph partitioning problems on graphs with edge capacities and vertex weights are considered. The problems of b-balanced and k-multiway separators are unified with the problem of minimum capacity p-separators. A new and simple O(log n) approximation algorithm is developed for minimum capacity p-separators yielding an O(log n) approximation algorithm for both b-balanced cuts and k-multiway separators. The results are enhanced by presenting a version of the algorithm that obtains an O(log OPT) approximation factor. The techniques involve spreading metrics that allow the minimum capacity p-separator problem to be formulated as an integer program. Generalizations of partitioning problems are also treated.

Original languageEnglish (US)
Pages639-648
Number of pages10
StatePublished - Jan 1 1997
Externally publishedYes
EventProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA
Duration: Jan 5 1997Jan 7 1997

Conference

ConferenceProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
CityNew Orleans, LA, USA
Period1/5/971/7/97

All Science Journal Classification (ASJC) codes

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Fast approximate graph partitioning algorithms'. Together they form a unique fingerprint.

Cite this