• DocumentCode
    2892907
  • Title

    Finding k-cuts within twice the optimal

  • Author

    Saran, Huzur ; Vazirani, Vijay V.

  • Author_Institution
    Dept. of Comput. Sci. & Eng., Indian Inst. of Tech., New Delhi, India
  • fYear
    1991
  • fDate
    1-4 Oct 1991
  • Firstpage
    743
  • Lastpage
    751
  • Abstract
    Two simple approximation algorithms are presented for the minimum k-cut problem. Each algorithm finds a k-cut having weight within a factor of (2-2/k) of the optimal. One of the algorithms is particularly efficient, requiring a total of only n -1 maximum flow computations for finding a set of near-optimal k-cuts, one for each value of k between 2 and n
  • Keywords
    approximation theory; computational complexity; graph theory; minimisation; approximation algorithms; maximum flow computations; minimum k-cut problem; weight; Approximation algorithms; Computer science; Helium; Partitioning algorithms; Polynomials; Very large scale integration;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
  • Conference_Location
    San Juan
  • Print_ISBN
    0-8186-2445-0
  • Type

    conf

  • DOI
    10.1109/SFCS.1991.185443
  • Filename
    185443
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2892907