Single Source Multiroute Flows and Cuts on Uniform Capacity Networks

by Henning Bruhn, Jakub Černý, Alexander Hall, Petr Kolman, and Jiří Sgall

Theory of Computing, Volume 4(1), pp. 1-20, 2008

Bibliography with links to cited articles

[1] Charu C. Aggarwal and James B. Orlin: On multiroute maximum flows in networks. Networks, 39:43-52, 2002. [Wiley:10.1002/net.10008].
[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin: Network Flows: Theory, Algorithms and Applications. Prentice-Hall, 1993.
[3] Yonatan Aumann and Yuval Rabani: An O(logk) approximate min-cut max-flow theorem and approximation algorithm. SIAM Journal on Computing, 27(1):291-301, 1998. [SICOMP:10.1137/S0097539794285983].
[4] Amitabha Bagchi, Amitabh Chaudhary, and Petr Kolman: Short length Menger's theorem and reliable optical routing. Theoretical Computer Science, 339:315-332, 2005. [TCS:10.1016/j.tcs.2005.03.009].
[5] Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman, and Christian Scheideler: Algorithms for fault-tolerant routing in circuit switched networks. SIAM Journal on Discrete Mathematics, 21:141-157, 2007. [SIDMA:10.1137/S0895480102419743].
[6] Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman, and Jiří Sgall: A simple combinatorial proof for the duality of multiroute flows and cuts. Technical Report 2004-662, Charles University, Prague, 2004.
[7] Georg Baier, Ekkehard Koehler, and Martin Skutella: The k-splittable flow problem. Algorithmica, 42(3-4):231-248, 2005. [Algorithmica:jtl3r3k633523486].
[8] Alok Baveja and Aravind Srinivasan: Approximation algorithms for disjoint paths and related routing and packing problems. Mathematics of Operations Research, 25(2):255-280, 2000.
[9] Henning Bruhn, Jakub Cerny, Alexander Hall, and Petr Kolman: Single source multiroute flows and cuts on uniform capacity networks. In Proc. 18th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'07), pp. 855-863. SIAM, 2007. [SODA:1283383.1283475].
[10] Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, and Amit Kumar: Approximation algorithms for the unsplittable flow problem. Algorithmica, 47(1):53-78, 2007. [Algorithmica:m5710531h2514815].
[11] Chandra Chekuri and Sanjeev Khanna: Edge-disjoint paths revisited. ACM Transactions on Algorithms, 3, 2007. [ACM:1290672.1290683].
[12] Israel Cidon, Raphael Rom, and Yuval Shavitt: Analysis of multi-path routing. IEEE/ACM Transactions on Networking, 7(6):885-896, 1999. [ACM:323983.323992].
[13] Y. Dinitz, N. Garg, and M. Goemans: On the single source unsplittable flow problem. Combinatorica, 19(1):17-41, 1999. [Springer:pg0crc9nqlfdmajj].
[14] D. Du and R. Chandrasekaran: The multiroute maximum flow problem revisited. Networks, 47(2):81-92, 2006. [Wiley:10.1002/net.20099].
[15] Donglei Du: Multiroute Flow Problem. Ph.D. thesis, The University of Texas at Dallas, 2003.
[16] Thomas Erlebach and Alexander Hall: NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. Journal of Scheduling, 7(3):223-241, 2004. [Springer:h57n764rq0124578].
[17] L. R. Ford and D. R. Fulkerson: Maximum flow through a network. Canad. J. Math., 8:399-404, 1956.
[18] Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis: Approximate max-flow min-cut theorems and their applications. SIAM Journal on Computing, 25(2):235-251, 1996. [SICOMP:10.1137/S0097539793243016].
[19] V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, and M. Yannakakis: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Journal of Computer and System Sciences, 67(3):473-496, 2003. [JCSS:10.1016/S0022-0000(03)00066-7].
[20] Koushik Kar, Murali Kodialam, and T. V. Lakshman: Routing restorable bandwidth guaranteed connections using maximum 2-route flows. IEEE/ACM Transactions on Networking, 11:772-781, 2003. [ACM:948928.948935].
[21] Wataru Kishimoto: A method for obtaining the maximum multiroute flows in a network. Networks, 27(4):279-291, 1996.
[22] Wataru Kishimoto and M. Takeuchi: On m-route flows in a network. IEICE Transactions, J-76-A(8):1185-1200, 1993. (in Japanese).
[23] J. M. Kleinberg: Single-source unsplittable flow. In Proc. 37th FOCS, pp. 68-77. IEEE Computer Society Press, 1996. [FOCS:10.1109/SFCS.1996.548465].
[24] Ronald Koch, Martin Skutella, and Ines Spenke: Approximation and complexity of k-splittable flows. In Proceedings of the Third Workshop on Approximation and Online Algorithms, volume 3879 of Lecture Notes in Computer Science, pp. 244-257. Springer, 2005. [WADS:l871111265475j11].
[25] Stavros G. Kolliopoulos and Clifford Stein: Approximation algorithms for single-source unsplittable flow. SIAM Journal on Computing, 31(3):919-946, 2002. [SICOMP:10.1137/S0097539799355314].
[26] Petr Kolman and Christian Scheideler: Simple on-line algorithms for the maximum disjoint paths problem. Algorithmica, 39(3):209-233, 2004. [Algorithmica:ppc4pcxagm69d4jv].
[27] Petr Kolman and Christian Scheideler: Improved bounds for the unsplittable flow problem. Journal of Algorithms, 61(1):20-44, 2006. [Elsevier:10.1016/j.jalgor.2004.07.006].
[28] Tom Leighton and Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787-832, November 1999. [JACM:331524.331526].
[29] N. Linial, E. London, and Yu. Rabinovich: The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995.
[30] Maren Martens and Martin Skutella: Flows on few paths: Algorithms and lower bounds. Networks, 48(2):68-76, 2006. [Wiley:10.1002/net.20121].
[31] Maren Martens and Martin Skutella: Length-bounded and dynamic k-splittable flows. In Operations Research Proceedings 2005, pp. 297-302, 2006. [Springer:w2u3032j1804481t].
[32] K. Menger: Zur allgemeinen Kurventheorie. Fundam. Math., 10:96-115, 1927.
[33] M. Skutella: Approximating the single source unsplittable min-cost flow problem. Mathematical Programming, Ser. B, 91(3):493-514, 2002. [Springer:txfq9gvdtw0cac0g].
[34] Aravind Srinivasan: Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. In Proc. 38th FOCS, pp. 416-425. IEEE Computer Society Press, 20-22 1997. [FOCS:10.1109/SFCS.1997.646130].

This file has been generated by bibtex2html 1.85.