• DocumentCode
    2785202
  • Title

    Approximation through multicommodity flow

  • Author

    Klein, Philip ; Agrawal, Ajit ; Ravi, R. ; Rao, Satish

  • Author_Institution
    Brown Univ., Providence, RI, USA
  • fYear
    1990
  • fDate
    22-24 Oct 1990
  • Firstpage
    726
  • Abstract
    The first approximate max-flow-min-cut theorem for general multicommodity flow is proved. It is used to obtain approximation algorithms for minimum deletion of clauses of a 2-CNF≡formula, via minimization problems, and other problems. Also presented are approximation algorithms for chordalization of a graph and for register sufficiency that are based on undirected and directed node separators
  • Keywords
    algorithm theory; computational complexity; approximation algorithms; max-flow-min-cut theorem; minimum deletion; multicommodity flow; Approximation algorithms; Laboratories; Minimization methods; Particle separators; Polynomials; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
  • Conference_Location
    St. Louis, MO
  • Print_ISBN
    0-8186-2082-X
  • Type

    conf

  • DOI
    10.1109/FSCS.1990.89595
  • Filename
    89595
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2785202