%% edited by LB 2008-04-06 DB 2008-04-13 @Article{AR:98, title = "An {$O(\log k)$} Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm", author = "Yonatan Aumann and Yuval Rabani", pages = "291--301", journal = "SIAM Journal on Computing", year = "1998", volume = "27", number = "1", eprint="sicomp:10.1137/S0097539794285983" } @Article{AO:02, author = "Charu C. Aggarwal and James B. Orlin", title = "On Multiroute Maximum Flows in Networks", journal = "Networks", volume = "39", year = "2002", pages = "43--52", eprint="wiley:10.1002/net.10008" } @Book{AMO:93, author = "R. K. Ahuja and T. L. Magnanti and J. B. Orlin", title = "Network Flows: Theory, Algorithms and Applications", year = "1993", publisher = "Prentice-Hall", } @Article{BCKS:07, author = {Amitabha Bagchi and Amitabh Chaudhary and Petr Kolman and Christian Scheideler}, title = {Algorithms for Fault-tolerant Routing in Circuit switched networks}, journal = "SIAM Journal on Discrete Mathematics", volume = "21", issue = "1", year = "2007", pages = "141--157", eprint="sidma:10.1137/S0895480102419743" } @TechReport{BCKS:04, author = {Amitabha Bagchi and Amitabh Chaudhary and Petr Kolman and {Ji\v {r}\'\i} Sgall}, title = {A simple combinatorial proof for the duality of multiroute flows and cuts}, institution = {Charles University}, year = 2004, number = {2004-662}, address = {Prague}, } @Article{BCK:05, author = "Amitabha Bagchi and Amitabh Chaudhary and Petr Kolman", title = "Short length {Menger}'s theorem and reliable optical routing", journal = "Theoretical Computer Science", volume = "339", year = "2005", pages = "315--332", eprint="tcs:10.1016/j.tcs.2005.03.009" } @Article{BKS:05, title = "The $k$-splittable Flow Problem", author = "Georg Baier and Ekkehard Koehler and Martin Skutella", journal = "Algorithmica", volume = 42, number = "3--4", pages = "231--248", year = "2005", eprint="algorithmica:jtl3r3k633523486" } @Article{BS:00, author = "Alok Baveja and Aravind Srinivasan", title = "Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems", journal = "Mathematics of Operations Research", volume = "25", number = "2", pages = "255--280", year = "2000", } @InProceedings{BCHK:07, title = "Single source multiroute flows and cuts on uniform capacity networks", author = "Henning Bruhn and Jakub \v{C}ern{\'y} and Alexander Hall and Petr Kolman", booktitle = "Proc. 18th Ann. {ACM}-{SIAM} Symposium on Discrete Algorithms ({SODA'07})", year = "2007", publisher = "SIAM", pages = "855--863", eprint="soda:1283383.1283475" } @Article{CCGK:07, title = "Approximation Algorithms for the Unsplittable Flow Problem", author = "Amit Chakrabarti and Chandra Chekuri and Anupam Gupta and Amit Kumar", journal = "Algorithmica", year = "2007", number = "1", volume = "47", pages = "53--78", eprint="algorithmica:m5710531h2514815" } @article{CK:07, author = "Chandra Chekuri and Sanjeev Khanna", title = "Edge-Disjoint Paths Revisited", journal = "ACM Transactions on Algorithms", volume = "3", issue = "4", year = "2007", eprint="acm:1290672.1290683" } @Article{CRS:99, author = "Israel Cidon and Raphael Rom and Yuval Shavitt", title = "Analysis of multi-path routing", journal = "IEEE\slash ACM Transactions on Networking", volume = "7", number = "6", pages = "885--896", year = "1999", eprint="acm:323983.323992" } @Article{DGG:99, author = "Y. Dinitz and N. Garg and M. Goemans", title = "On the Single Source Unsplittable Flow Problem", journal = "Combinatorica", volume = "19", number=1, pages = "17--41", year = "1999", eprint="springer:pg0crc9nqlfdmajj"} @Article{DCH:06, author = "D. Du and R. Chandrasekaran", title = "The multiroute maximum flow problem revisited", journal = "Networks", volume = "47", number = "2", pages = {81--92}, year = "2006", eprint="wiley:10.1002/net.20099" } @Book{Du:03, author = {Donglei Du}, title = {Multiroute Flow Problem}, publisher = {Ph.D. thesis, The University of Texas at Dallas}, year = {2003} } @Article{EH:04, title = "{NP}-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow", author = "Thomas Erlebach and Alexander Hall", journal = "Journal of Scheduling", year = "2004", volume = "7", number = "3", pages = "223--241", eprint="springer:h57n764rq0124578" } @Article{FF:56, author = {L. R. Ford and D. R. Fulkerson}, title = {Maximum flow through a network}, journal = {Canad. J. Math.}, year = 1956, volume = 8, pages = {399--404} } @Article{GVY:96, title = "Approximate Max-Flow Min-Cut Theorems and Their Applications", author = "Naveen Garg and Vijay V. Vazirani and Mihalis Yannakakis", pages = "235--251", journal = "SIAM Journal on Computing", year = "1996", volume = "25", number = "2", eprint="sicomp:10.1137/S0097539793243016" } @Article{GKRSY:03, author = "V. Guruswami and S. Khanna and R. Rajaraman and B. Shepherd and M. Yannakakis", title = "Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems", journal = "Journal of Computer and System Sciences", volume = 67, number = 3, pages = "473--496", year = "2003", eprint="jcss:10.1016/S0022-0000(03)00066-7" } @Article{KKL:03, author = "Koushik Kar and Murali Kodialam and T. V. Lakshman", title = "Routing restorable bandwidth guaranteed connections using maximum 2-route flows", journal = "IEEE\slash ACM Transactions on Networking", year = 2003, volume = 11, issue = 5, pages = "772--781", eprint="acm:948928.948935" } @Article{KT:93, author = "Wataru Kishimoto and M. Takeuchi", title = "On $m$-route flows in a network", journal = "IEICE Transactions", volume = "J-76-A", year = "1993", number = "8", pages = "1185--1200", language = "Japanese", note = "(in Japanese)" } @Article{Kishimoto:96, author = "Wataru Kishimoto", title = "A Method for Obtaining the Maximum Multiroute Flows in a Network", journal = "Networks", volume = "27", number=4, year = "1996", pages = "279--291", removeeprint={wiley:10.1002/(SICI)1097-0037(199607)27:4<279::AID-NET3>3.0.CO;2-D} } @InProceedings{Kleinberg:96, author = "J. M. Kleinberg", title = "Single-source unsplittable flow", booktitle = "Proc. 37th FOCS", publisher = "IEEE Computer Society Press", pages = "68--77", year = "1996", eprint="focs:10.1109/SFCS.1996.548465" } @InProceedings{KSS:05, title = "Approximation and Complexity of $k$-Splittable Flows", author = "Ronald Koch and Martin Skutella and Ines Spenke", year = "2005", volume = "3879", booktitle = "Proceedings of the Third Workshop on Approximation and Online Algorithms", pages = "244--257", series = "Lecture Notes in Computer Science", publisher = "Springer", eprint="wads:l871111265475j11" } @Article{KS:02a, author = "Stavros G. Kolliopoulos and Clifford Stein", title = "Approximation Algorithms for Single-Source Unsplittable Flow", journal = "SIAM Journal on Computing", volume = "31", number = "3", pages = "919--946", year = "2002", eprint="sicomp:10.1137/S0097539799355314" } @Article{KS:04, author = "Petr Kolman and Christian Scheideler", title = "Simple On-Line Algorithms for the Maximum Disjoint Paths Problem", journal = "Algorithmica", volume = "39", number = "3", pages = "209--233", year = "2004", eprint="algorithmica:ppc4pcxagm69d4jv" } @comment{ note = "Preliminary version in Proc. 13th Ann. {ACM} Symposium on Parallel Algorithms and Architectures (SPAA'01)" } @Article{KS:06, title = "Improved bounds for the unsplittable flow problem", author = "Petr Kolman and Christian Scheideler", journal = "Journal of Algorithms", year = "2006", number = "1", volume = "61", pages = "20--44", eprint="elsevier:10.1016/j.jalgor.2004.07.006" } @Article{LR:99, author = "Tom Leighton and Satish Rao", title = "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms", journal = "Journal of the ACM", volume = "46", number = "6", pages = "787--832", month = nov, year = "1999", eprint="jacm:331524.331526" } @comment{ note = "Preliminary version in Proc. 29th FOCS (1988)"} @article{LLR:95 , author="N. Linial and E. London and {Yu}. Rabinovich" , title="The geometry of graphs and some of its algorithmic applications" , journal="Combinatorica" , volume=15, number=2 , pages="215--245" , year=1995, comment="springer:h16248312kq1t054" } @comment{ note ="Preliminary version in Proc. 35th FOCS (1994)"} @InProceedings{MS:05, author = "Maren Martens and Martin Skutella", title = "Length-Bounded and Dynamic k-Splittable Flows", booktitle = "Operations Research Proceedings 2005", year = "2006", pages = {297--302}, eprint="springer:w2u3032j1804481t" } @article{MS:06, author = "Maren Martens and Martin Skutella", title = "Flows on Few Paths: Algorithms and Lower Bounds", journal = "Networks", year = 2006, volume = 48, number = "2", pages = {68--76}, eprint="wiley:10.1002/net.20121" } @comment{ note = "Preliminary version in Proc. 12th Ann. European Symposium on Algorithms (ESA'04)"} @Article{Menger:27, author = {K. Menger}, title = {Zur Allgemeinen {Kurventheorie}}, journal = {Fundam. Math.}, year = 1927, volume = 10, pages = {96--115} } @Article{Skutella:02, author = "M. Skutella", title = "Approximating the single source unsplittable min-cost flow problem", journal = "Mathematical Programming, Ser. B", volume = 91, number = 3, pages = {493--514}, year = "2002", eprint="springer:txfq9gvdtw0cac0g" } @InProceedings{Srinivasan:97, title = "Improved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems", author = "Aravind Srinivasan", pages = "416--425", booktitle = "Proc. 38th FOCS", publisher = "IEEE Computer Society Press", month = "20--22 ", year = "1997", eprint="focs:10.1109/SFCS.1997.646130" }