Approximation through multicommodity flow
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 726-737vol.2
- https://doi.org/10.1109/fscs.1990.89595
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 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.Keywords
This publication has 21 references indexed in Scilit:
- Approximation algorithms for combinatorial problemsPublished by Elsevier ,2007
- Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacitiesPublished by Association for Computing Machinery (ACM) ,1990
- Some nested dissection order is nearly optimalInformation Processing Letters, 1988
- A New Implementation of Sparse Gaussian EliminationACM Transactions on Mathematical Software, 1982
- Edge-Deletion ProblemsSIAM Journal on Computing, 1981
- Computing the Minimum Fill-In is NP-CompleteSIAM Journal on Algebraic Discrete Methods, 1981
- Applications of a Planar Separator TheoremSIAM Journal on Computing, 1980
- Generalized Nested DissectionSIAM Journal on Numerical Analysis, 1979
- New problems complete for nondeterministic log spaceTheory of Computing Systems, 1976
- Multi-Commodity Network FlowsOperations Research, 1963