{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:47:40Z","timestamp":1774421260048,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,10,2]],"date-time":"2009-10-02T00:00:00Z","timestamp":1254441600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2010,1]]},"DOI":"10.1007\/s11590-009-0147-4","type":"journal-article","created":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T07:41:14Z","timestamp":1254382874000},"page":"37-55","source":"Crossref","is-referenced-by-count":12,"title":["A fast heuristic algorithm for the maximum concurrent k-splittable flow problem"],"prefix":"10.1007","volume":"4","author":[{"given":"Massimiliano","family":"Caramia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonino","family":"Sgalambro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,10,2]]},"reference":[{"key":"147_CR1","volume-title":"Network Flows: Theory Algorithms and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja R.K., Magnanti T.L., Orlin J.B.: Network Flows: Theory Algorithms and Applications. Prentice Hall Inc., Englewood Cliffs (1993)"},{"key":"147_CR2","doi-asserted-by":"crossref","first-page":"622","DOI":"10.1109\/43.920691","volume":"20","author":"C. Albrecht","year":"2001","unstructured":"Albrecht C.: Global routing by new approximation algorithms for multicommodity flow. IEEE Trans. Comput. Aided Des. Integr. Circuit Syst. 20, 622\u2013632 (2001)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuit Syst."},{"key":"147_CR3","doi-asserted-by":"crossref","unstructured":"Andrews, M., Zhang, L.: Hardness of the undirected congestion minimization problem. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005)","DOI":"10.1145\/1060590.1060633"},{"key":"147_CR4","doi-asserted-by":"crossref","unstructured":"Azar, Y., Regev, O.: Strongly polynomial algorithms for the unsplittable flow problem. In: Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization, pp. 15\u201329 (2001)","DOI":"10.1007\/3-540-45535-3_2"},{"key":"147_CR5","unstructured":"Badics, T.: GENRMF. (1991). ftp:\/\/dimacs.rutgers.edu\/pub\/netflow\/generators\/network\/genrmf\/"},{"key":"147_CR6","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s101070100254","volume":"91","author":"D. Bienstock","year":"2002","unstructured":"Bienstock D., Raskina O.: Asymptotic analysis of the flow deviation method for the maximum concurrent flow problem. Math. Program. Ser. B 91, 479\u2013492 (2002)","journal-title":"Math. Program. Ser. B"},{"key":"147_CR7","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/s00453-005-1167-9","volume":"42","author":"G. Baier","year":"2005","unstructured":"Baier G., K\u00f6hler E., Skutella M.: On the k-splittable flow problem. Algorithmica 42, 231\u2013248 (2005)","journal-title":"Algorithmica"},{"issue":"2","key":"147_CR8","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s11590-007-0055-4","volume":"2","author":"M. Caramia","year":"2008","unstructured":"Caramia M., Sgalambro A.: An exact approach for the maximum concurrent k-splittable flow problem. Optim. Lett. 2(2), 251\u2013265 (2008)","journal-title":"Optim. Lett."},{"issue":"2","key":"147_CR9","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/j.jda.2007.03.001","volume":"6","author":"M. Caramia","year":"2008","unstructured":"Caramia M., Sgalambro A.: On the approximation of the single source k-splittable flow problem. J. Discrete Algorithms 6(2), 277\u2013289 (2008)","journal-title":"J. Discrete Algorithms"},{"key":"147_CR10","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Naor, J.: New hardness results for congestion minimization and machine scheduling. In: Proceedings of the 36th Annual ACM Symposium of Theory of Computing, pp. 28\u201334, Chicago, IL (2004)","DOI":"10.1145\/1007352.1007364"},{"key":"147_CR11","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s004930050043","volume":"19","author":"Y. Dinitz","year":"1999","unstructured":"Dinitz Y., Garg N., Goemans M.X.: On the single-source unsplittable flow problem. Combinatorica 19, 17\u201341 (1999)","journal-title":"Combinatorica"},{"key":"147_CR12","doi-asserted-by":"crossref","unstructured":"Fratta, L., Gerla, M., Kleinrock, L.: The flow deviation method: an approach to store-and-forward computer-communication network design. Networks 3 (1973)","DOI":"10.1002\/net.3230030202"},{"key":"147_CR13","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02288321","volume":"13","author":"D. Goldfarb","year":"1988","unstructured":"Goldfarb D., Grigoriadis M.: A computational comparison of the Dinic and network simplex methods for maximum flow. Ann. Oper. Res. 13, 83\u2013123 (1988)","journal-title":"Ann. Oper. Res."},{"key":"147_CR14","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Khanna, S., Rajaraman, R., Sheperd, B., Yannakakis, M.: Near optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 19\u201328 (1999)","DOI":"10.1145\/301250.301262"},{"key":"147_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0167-9260(01)00020-7","volume":"31","author":"J. Hu","year":"2001","unstructured":"Hu J., Sapatnekar S.S.: A survey on multi-net global routing for integrated circuits. Integration VLSI J. 31, 1\u201349 (2001)","journal-title":"Integration VLSI J."},{"key":"147_CR16","unstructured":"Kleinberg, J.: Approximation algorithms for disjoint paths problems. PhD thesis, MIT (1996)"},{"key":"147_CR17","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Single-source unsplittable flow. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 68\u201377 (1996)","DOI":"10.1109\/SFCS.1996.548465"},{"key":"147_CR18","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Tardos, E.: Disjoint paths in densely embedded graphs. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp. 52\u201361 (1995)","DOI":"10.1109\/SFCS.1995.492462"},{"key":"147_CR19","doi-asserted-by":"crossref","unstructured":"Koch, R., Skutella, M., Spenke, I.: Approximation and complexity of k-splittable flows. Technical Report (2005)","DOI":"10.1007\/11671411_19"},{"key":"147_CR20","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S.G.: Improved approximation algorithms for unsplittable flow problems. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pp. 426\u2013435 (1997)","DOI":"10.1109\/SFCS.1997.646131"},{"issue":"1","key":"147_CR21","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.ipl.2004.12.009","volume":"9","author":"S.G. Kolliopoulos","year":"2005","unstructured":"Kolliopoulos S.G.: Minimum-cost single-source 2-splittable flow. Inf. Process. Lett. 9(1), 15\u201318 (2005)","journal-title":"Inf. Process. Lett."},{"key":"147_CR22","unstructured":"Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 184\u2013193 (2002)"},{"issue":"2","key":"147_CR23","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1002\/net.20121","volume":"48","author":"M. Martens","year":"2006","unstructured":"Martens M., Skutella M.: Flows on few paths: algorithms and lower bounds. Networks 48(2), 68\u201376 (2006)","journal-title":"Networks"},{"key":"147_CR24","doi-asserted-by":"crossref","unstructured":"M\u00fcller, D.: Optimizing Yield in Global Routing. ICCAD (2006)","DOI":"10.1109\/ICCAD.2006.320161"},{"issue":"4","key":"147_CR25","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan P., Thompson C.: Randomized rounding: a technique for provable good algorithms and algorithmic proofs. Combinatorica 7(4), 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"147_CR26","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF01759035","volume":"6","author":"P. Raghavan","year":"1991","unstructured":"Raghavan P., Thompson C.: Multiterminal global routing: a deterministic approximation scheme. Algorithmica 6, 73\u201382 (1991)","journal-title":"Algorithmica"},{"key":"147_CR27","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1145\/77600.77620","volume":"37","author":"F. Shahrokhi","year":"1990","unstructured":"Shahrokhi F., Matula D.W.: The maximum concurrent flow problem. J ACM 37, 318\u2013334 (1990)","journal-title":"J ACM"},{"key":"147_CR28","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/s101070100260","volume":"91","author":"M. Skutella","year":"2002","unstructured":"Skutella M.: Approximating the single source unsplittable min-cost flow problem. Math. Programm. 91, 493\u2013514 (2002)","journal-title":"Math. Programm."},{"key":"147_CR29","doi-asserted-by":"crossref","unstructured":"Vygen, J.: Near-optimum global routing with coupling, delay bounds, and power consumption. In: Proceedings of the 10th International IPCO Conference, pp. 308\u2013324. Springer, New York (2004)","DOI":"10.1007\/978-3-540-25960-2_24"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-009-0147-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-009-0147-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-009-0147-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T13:33:47Z","timestamp":1739367227000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-009-0147-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,2]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["147"],"URL":"https:\/\/doi.org\/10.1007\/s11590-009-0147-4","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,2]]}}}