David R. Karger
- 1.H. Chernoff. "A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations". Annals of Mathematical Statistics, 23:493-509# 1952.Google Scholar
Cross Ref
- 2.E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov. "On the structure of a family of minimal weighted cuts in a graph". In A. A. Fridman, editor, .Studies in Discrete Optimization, pages 290-306. Nauka Publ., 1976.Google Scholar
- 3.J. Edmonds. "Minimum partition of a matroid into independents subsets". Journal of Research of the National Bureau of Standards, 69:67-72, 1965.Google ScholarCross Ref
- 4.D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. "Sparsificationma technique for speeding up dynamic graph algorithms". In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 60-69, Oct. 1992.Google ScholarDigital Library
- 5.K. P. Eswaran and R. E. Tarjan. "Augmentation problems". SIAM Journal on Computing, 5:653-665# 1976.Google ScholarCross Ref
- 6.L. R. Ford, jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962.Google Scholar
- 7.H.N. Gabow. "A matroid approach to finding edge connectivity and packing arborescences". In Proceedings of the 23rd Annual Symposium on Theory of Computing. ACM Press, May 1991. Google ScholarDigital Library
- 8.H. N. Gabow. "Applications of a poset representation to edge connectivity and graph rigidity", in Proceedings of the 32'#d Annual Symposium on Foundations of Computer Science, pages 812-821, Oct. 1991. Google ScholarDigital Library
- 9.H. N. Gabow. "A framework for cost-scaling algorithms for submodular flow problems". In Proceedings of the 34#h Annual Symposium on Foundations of Computer Science, pages 449-458, Nov. 1993.Google ScholarDigital Library
- 10.H. N. Gabow, M. X. Goemans, and D. P. Williamson. "An efficient approximation algorithm for the survivable network design problem", in Proceedings of the Third MPS Conference on Integer Programming and Combinatorial Optimization# pages 57-74, 1993.Google Scholar
- 11.M. X. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, E. Tardos, and D. Williamson. "Improved approximation algorithms for network design problems". In Proceedings of the 5th A CM-SIAM Symposium on Discrete Algorithms, pages 223-232, Jan. 1994. Google ScholarDigital Library
- 12.R. E. Gomory and T. C. Hu. "Multi-terminal network flows". Journal of the Society of Industrial and Applied Mathematics, 9(4):551-570, Dec. 1961.Google ScholarCross Ref
- 13.D. R. Karger. "Global min-cuts in 7tAlC and other ramifications of a simple mincut algorithm". In Proceedings of the 4tu A CM-SIAM Symposium on Discrete Algorithms, pages 21-30, Jan. 1993. Google ScholarDigital Library
- 14.D. R. Karger. "Random sampling in matroids, with applications to graph connectivity and minimum spanning trees". In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993.Google ScholarDigital Library
- 15.D. R. Karger. "Using randomized sparsification to approximate minimum cuts". In Proceedings of the 5#h A CM-SIAM Symposium on Discrete Algorithms, Jan. 1994. Google ScholarDigital Library
- 16.D. R. Karger and C. Stein. "An (P(n:) algorithm for minimum cuts". In Proceedings of the 25th Annual A CM Symposium on Theory of Computing, pages 757- 765, 1993. Google ScholarDigital Library
- 17.S. Khuller and B_ Schieber. "Ei#cient parallel algorithms for testing connectivity and finding disjoint st paths in graphs". SIAM Journal on Computing, 20(2):352-375, Apr. 1991. Google ScholarDigital Library
- 18.S. Khuller and U. Vishkin. "Biconnectivity approximations and graph carvings". In Proceedings of the 24#h Annual A CM Symposium on Theory of Computing, pages 759-770, May 1992. Google ScholarDigital Library
- 19.P. N. Klein, C. Stein, and E. Tardos. "Leighton-Rao might be practical: Faster approximation algorithms for concurrent flow with uniform capacities", in Proceedings of the 22"#d Annual Symposium on Theory of Computing, pages 310-321. ACM, May 1990. Google ScholarDigital Library
- 20.P. N. Klein and R. E. Tarjan. "A linear-time algorit:hm for minimum spanning tree". In Proceedings of the 26th A CM Symposium on Theory of Computing, 1994. To appear. Google ScholarDigital Library
- 21.T. Leighton and S. Rao. "An approximate maxflow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms". In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 422-4;31. IEEE, Oct. 1988.Google ScholarDigital Library
- 22.D.W. Matula. "A linear time 2 +e approximation algorithm for edge connectivity". In Proceedings of the Ath A CM-SIAM Symposium on Discrete Algorithms, pages 500-504, Jan. 1993. Google ScholarDigital Library
- 23.H. Nagamochi and T. Ibaraki. On max-flow min-cut and integral flow properties for multicommodity flows in directed networks. Information Processing Letters, 31:279-285, 1989. Google ScholarDigital Library
- 24.H. Nagamochi and T. Ibaraki. "Computing edge connectivity in multigraphs and capacitated graphs". SIAM Journal of Discrete Mathematics, 5(1):54-66, Feb. 1992. Google ScholarDigital Library
- 25.H. Nagamochi and T. Ibaraki. "Linear time algorithms for finding k-edge connected and k-node connected spanning subgraphs. Algorithmica, 7:583-596, 1992.Google ScholarCross Ref
- 26.C. S. J. A. Nash-Williams. "Well-balanced orientations of finite graphs and unobtrusive odd-vertex-pairings/'. In W. T. Tutte, editor, Recent Progress in Combinatorics, pages 133-149. Academic Press, 1969.Google Scholar
- 27.P. Raghavan and C. Thompson. "Probabilistic construction of deterministic algorithms' Approximate packing integer programs". Journal of Computer and System Sciences, 37(2):130-43# Oct. 1988. Google ScholarDigital Library
- 28.R. E. Tarjan. Data Structures and Network Algorithms, volume 44 of CBMS.NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, 1983. Google ScholarDigital Library
- 29.D. Williamson, M. X. Goemans, M. Mihail, and V. V. Vazirani. "A primal-dual approximation algorithm for generalized steiner problems", in Proceedings of the 25th Annual A CM Symposium on Theory of Computing, pages 708-717, May 1993. Google ScholarDigital Library
Index Terms
- Random sampling in cut, flow, and network design problems
Recommendations
Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems
We present a column-generation model and branch-and-price-and-cut algorithm for origin-destination integer multicommodity flow problems. The origin-destination integer multicommodity flow problem is a constrained version of the linear multicommodity ...
New partial aggregations for multicommodity network flow problems: An application to the fixed-charge network design problem
AbstractWhen solving hard multicommodity network flow problems using an LP-based approach, the number of commodities is a driving factor in the speed at which the LP can be solved, as it is linear in the number of constraints and variables. ...
Highlights- We introduce new commodity representations for multicommodity network flow problems.
Integer programming models and branch-and-cut approaches to generalized {0,1,2}-survivable network design problems
In this article, we introduce the Generalized $$\{0,1,2\}$${0,1,2}-Survivable Network Design Problem ($$\{0,1,2\}$${0,1,2}-GSNDP) which has applications in the design of backbone networks. Different mixed integer linear programming formulations are ...
Comments