Approximate max-integral-flow/min-multicut theorems. (English) Zbl 1192.90236
Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 539-545, electronic only (2004).
MSC:
| 90C35 | Programming involving graphs or networks |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Y. Aumann and Y. Rabani. An O (log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM Journal on Computing, 27(1):291-301, 1998.]] 10.1137/S0097539794285983 · Zbl 0910.05038 |
| [2] | A. Bogdanov, K. Obata, and L. Trevisan. A lower bound for testing 3-colorability. In IEEE Symposium on Foundations of Computer Science, pages 93-102, 2002.]] |
| [3] | B. Bollobás, P. Erdös, M. Simonovits, and E. Szemerédi. Extremal graphs without large forbidden subgraphs. Annals of Discrete Mathematics, 3:29-41, 1978.]] · Zbl 0375.05034 |
| [4] | C. Chekuri and S. Khanna. Edge disjoint paths revisited. In ACM-SIAM Symposium on Discrete Algorithms, pages 628-637, 2003.]] · Zbl 1092.68620 |
| [5] | E. Dahlhaus, D. Johnson, C. Papadimitriou, P. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23:864-894, 1994.]] 10.1137/S0097539792225297 · Zbl 0809.68075 |
| [6] | L. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8, 1956.]] · Zbl 0073.40203 |
| [7] | N. Garg, V. V. Vazirani, and M. Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. In ACM Symposium on Theory of Computing, pages 698-707, 1993.]] 10.1145/167088.167266 · Zbl 1310.05198 |
| [8] | N. Garg, V. V. Vazirani, and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18:3-20, 1997.]] · Zbl 0873.68075 |
| [9] | O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653-750, 1998.]] 10.1145/285055.285060 · Zbl 1065.68575 |
| [10] | O. Goldreich and D. Ron. Property testing in bounded degree graphs. In ACM Symposium on Theory of Computing, pages 406-415, 1997.]] 10.1145/258533.258627 · Zbl 0963.68154 |
| [11] | O. Günlük. A new min-cut max-flow ratio for multicommodity flows. In Integer Programming and Combinatorial Optimization, pages 54-66, 2002.]] · Zbl 1049.90108 |
| [12] | R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85-103, New York, NY, 1972. Plenum Press.]] · Zbl 1467.68065 |
| [13] | P. Klein, S. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In ACM Symposium on Theory of Computing, pages 682-690, 1993.]] 10.1145/167088.167261 · Zbl 1310.90017 |
| [14] | J. Kleinberg. Approximation algorithms for disjoint paths problems. Ph. D. Thesis, MIT, Cambridge, MA, 1996.]] |
| [15] | S. G. Kolliopoulos and C. Stein. Approximating disjoint-path problems using greedy algorithms and packing integer programs. In Integer Programming and Combinatorial Optimization, 1998.]] |
| [16] | J. Komlós. Covering odd cycles. Combinatorica, pages 393-400, 1997.]] · Zbl 0902.05036 |
| [17] | F. T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multi-commodity flow problems with applications to approximation algorithms. Journal of the ACM, 46(6), 1999.]] · Zbl 1065.68666 |
| [18] | N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215-245, 1995.]] · Zbl 0827.05021 |
| [19] | S. Plotkin and E. Tardos. Improved bounds on the max-flow min-cut ratio for multicommodity flows. In ACM Symposium on Theory of Computing, pages 691-697, 1993.]] 10.1145/167088.167263 · Zbl 1310.68095 |
| [20] | K. Varadarajan and G. Venkataraman. Graph decomposition and a greedy algorithm for edge-disjoint paths. In ACM-SIAM Symposium on Discrete Algorithms, 2004.]] |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
