STOC Conference 1991 Conference Paper
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Ajit Agrawal
- Philip N. Klein
- R. Ravi 0001
Author name cluster
Ajit Agrawal
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
1 author row
Possible papers
2FOCS Conference 1990 Conference Paper
Approximation through Multicommodity Flow
- Philip N. Klein
- Ajit Agrawal
- R. Ravi 0001
- Satish Rao
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 identical to 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. >