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(log k) 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 Černý, 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].