Title :
Approximation through multicommodity flow
Author :
Klein, Philip ; Agrawal, Ajit ; Ravi, R. ; Rao, Satish
Author_Institution :
Brown Univ., Providence, RI, USA
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;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89595
