{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:24:13Z","timestamp":1787325853688,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>In this paper we consider the k edge\u2010disjoint paths problem (k\u2010EDP), a generalization of the well\u2010known edge\u2010disjoint paths problem. Given a graph $G=(V,E)$ and a set of terminal pairs (or requests) T, the problem is to find a maximum subset of the pairs in T for which it is possible to select paths such that each pair is connected by k edge\u2010disjoint paths and the paths for different pairs are mutually disjoint. To the best of our knowledge, no nontrivial result is known for this problem for $k&gt;1$. To measure the performance of our algorithms we use the recently introduced flow number F of a graph. This parameter is known to fulfill $F=O(\\Delta \\alpha^{-1} \\log n)$, where $\\Delta$ is the maximum degree, $\\alpha$ is the edge expansion of G, and n is the number of vertices in G. We show that a simple greedy online algorithm achieves a competitive ratio of $O(k^3 F)$ which naturally extends the best known bound of $O(F)$ for $k=1$ to higher k. To achieve this competitive ratio, we introduce a new method of converting a system of k disjoint paths into a system of k length\u2010bounded disjoint paths. We also show that any deterministic online algorithm has a competitive ratio of $\\Omega(k F)$. In addition, we study the k disjoint flows problem (k\u2010DFP), which is a generalization of the previously studied unsplittable flow problem. The difference between the k\u2010DFP and the k\u2010EDP is that now we consider a graph with edge capacities and our requests are allowed to have arbitrary demands $d_i$. The aim is to find a subset of requests of maximum total demand for which it is possible to select flow paths such that all the capacity constraints are maintained and each selected request with demand $d_i$ is connected by k disjoint paths, each of flow value $d_i\/k$. The k\u2010EDP and k\u2010DFP problems have important applications in fault\u2010tolerant (virtual) circuit switching, which plays a key role in optical networks.<\/jats:p>","DOI":"10.1137\/s0895480102419743","type":"journal-article","created":{"date-parts":[[2007,2,15]],"date-time":"2007-02-15T17:53:38Z","timestamp":1171562018000},"page":"141-157","source":"Crossref","is-referenced-by-count":1,"title":["Algorithms for Fault\u2010Tolerant Routing in Circuit\u2010Switched Networks"],"prefix":"10.1137","volume":"21","author":[{"given":"Amitabha","family":"Bagchi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amitabh","family":"Chaudhary","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr","family":"Kolman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,2,15]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, and S. Plotkin,\n                      Throughput\u2010competitive on\u2010line routing\n                      , in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1993, pp. 32\u201340.","DOI":"10.1109\/SFCS.1993.366884"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1172-z"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.03.009"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"G. Baier, E. K\u00f6hler, and M. Skutella,\n                      \n                        On the\n                        k\n                        \u2010splittable flow problem\n                      \n                      , in Proceedings of the 10th Annual European Symposium on Algorithms (ESA), Lecture Notes in Comput. Sci. 2461, Springer, Berlin, 2002, pp. 101\u2013113.","DOI":"10.1007\/3-540-45749-6_13"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.2.255.12228"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0179-6"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s,\n                      Modern Graph Theory\n                      , Springer, New York, 1998.","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. Chakrabarti, C. Chekuri, A. Gupta, and A. Kumar,\n                      Approximation algorithms for the unsplittable flow problem\n                      , in Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), Lecture Notes in Comput. Sci. 2462, Springer, Berlin, 2002.","DOI":"10.1007\/3-540-45753-4_7"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna, and F. B. Shepherd,\n                      The all\u2010or\u2010nothing multicommodity flow problem\n                      , in Proceedings of the 36th annual ACM Symposium on Theory of Computing (STOC), 2004, pp. 156\u2013165.","DOI":"10.1145\/1007352.1007383"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver,\n                      Combinatorial Optimization\n                      , John Wiley, New York, 1997.","DOI":"10.1002\/9781118033142"},{"key":"R12","unstructured":"P. Erdo\u02dds and L. Lov\u00e1sz,\n                      Problems and results on 3\u2010chromatic hypergraphs and some related questions\n                      , in Infinite and Finite Sets (to Paul Erdo\u02dds on his 60th birthday), A. Hajnal, R. Rado, and V. S\u00f3s, eds., North\u2013Holland, Amsterdam, 1975, pp. 609\u2013627."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00066-7"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"R15","unstructured":"J. Kleinberg,\n                      Approximation Algorithms for Disjoint Paths Problems\n                      , Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 1996."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"R. Koch, M. Skutella, and I. Spenke,\n                      \n                        Approximation and complexity of\n                        k\n                        \u2010splittable flows\n                      \n                      , in Proceedings of the 3rd Workshop on Approximation and Online Algorithms (WAOA), Lecture Notes in Comput. Sci. 3879, Springer, Berlin, 2005, pp. 244\u2013257.","DOI":"10.1007\/11671411_19"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.07.006"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1086-1"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1002\/net.20121"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"M. Martens and M. Skutella,\n                      Length\u2010bounded and dynamic k\u2010splittable flows\n                      , in Operations Research Proceedings 2005, Springer, Berlin, 2006, pp. 297\u2013302.","DOI":"10.1007\/3-540-32539-5_47"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"C. Scheideler,\n                      Universal Routing Strategies for Interconnection Networks\n                      , Lecture Notes in Comput. Sci. 1390, Springer, Berlin, 1998.","DOI":"10.1007\/BFb0052928"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480102419743","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:23:30Z","timestamp":1787322210000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480102419743"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/S0895480102419743"],"URL":"https:\/\/doi.org\/10.1137\/s0895480102419743","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}