{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,15]],"date-time":"2023-04-15T00:55:28Z","timestamp":1681520128372},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,5,21]],"date-time":"2009-05-21T00:00:00Z","timestamp":1242864000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s10878-009-9225-x","type":"journal-article","created":{"date-parts":[[2009,5,20]],"date-time":"2009-05-20T16:10:20Z","timestamp":1242835820000},"page":"272-293","source":"Crossref","is-referenced-by-count":3,"title":["Flows with unit path capacities and related packing and\u00a0covering problems"],"prefix":"10.1007","volume":"18","author":[{"given":"Maren","family":"Martens","sequence":"first","affiliation":[]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,5,21]]},"reference":[{"key":"9225_CR1","volume-title":"Network flows","author":"RK Ahuja","year":"1993","unstructured":"Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows. Prentice-Hall, Englewood Cliffs"},{"issue":"1","key":"9225_CR2","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1137\/050636899","volume":"37","author":"M Andrews","year":"2007","unstructured":"Andrews M, Zhang L (2007) Hardness of the undirected congestion minimization problem. SIAM J Comput 37(1):112\u2013131","journal-title":"SIAM J Comput"},{"key":"9225_CR3","doi-asserted-by":"crossref","unstructured":"Baier G, Erlebach T, Hall A, K\u00f6hler E, Schilling H, Skutella M (2006) Length-bounded cuts and flows. In: Proceedings of the 33rd international colloquium on automata, languages and programming, pp\u00a0679\u2013690","DOI":"10.1007\/11786986_59"},{"key":"9225_CR4","first-page":"83","volume":"45","author":"L Bartholdi","year":"1999","unstructured":"Bartholdi L (1999) Counting paths in graphs. Enseign Math 45:83\u2013131","journal-title":"Enseign Math"},{"key":"9225_CR5","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1287\/moor.25.2.255.12228","volume":"25","author":"A Baveja","year":"2000","unstructured":"Baveja A, Srinivasan A (2000) Approximation algorithms for disjoint paths and related routing and packing problems. Math Oper Res 25:255\u2013280","journal-title":"Math Oper Res"},{"key":"9225_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri C, Khanna S (2007). Edge-disjoint paths revisited. ACM Trans Algorithms (TALG), 3(4)","DOI":"10.1145\/1290672.1290683"},{"key":"9225_CR7","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connection with graphs. Numer Math 1:269\u2013271","journal-title":"Numer Math"},{"key":"9225_CR8","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1287\/opre.17.3.395","volume":"17","author":"SE Dreyfus","year":"1969","unstructured":"Dreyfus SE (1969) An appraisal of some shortest path algorithms. Oper Res 17:395\u2013412","journal-title":"Oper Res"},{"key":"9225_CR9","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1137\/S0097539795290477","volume":"28","author":"D Eppstein","year":"1998","unstructured":"Eppstein D (1998) Finding the k shortest paths. SIAM J Comput 28:652\u2013673","journal-title":"SIAM J Comput"},{"issue":"4","key":"9225_CR10","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/S0895480199355754","volume":"13","author":"LK Fleischer","year":"2000","unstructured":"Fleischer LK (2000) Approximating fractional multicommodity flow independent of the number of commodities. SIAM J Discrete Math 13(4):505\u2013520","journal-title":"SIAM J Discrete Math"},{"key":"9225_CR11","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford LR, Fulkerson DR (1956) Maximal flow through a network. Can J Math 8:399\u2013404","journal-title":"Can J Math"},{"key":"9225_CR12","unstructured":"Fox BL (1975) k-th shortest paths and applications to the probabilistic networks. In: ORSA\/TIMS joint national meeting, 23:B263"},{"key":"9225_CR13","doi-asserted-by":"crossref","unstructured":"Garg N, K\u00f6nemann J (1998) Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: Proceedings of the 39th annual IEEE symposium on foundations of computer science, pp\u00a0300\u2013309","DOI":"10.1109\/SFCS.1998.743463"},{"key":"9225_CR14","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0378-3758(93)90038-8","volume":"34","author":"I Gessel","year":"1993","unstructured":"Gessel I (1993) Counting paths in Young\u2019s lattice. J Stat Plan Inference 34:125\u2013134","journal-title":"J Stat Plan Inference"},{"issue":"1.2","key":"9225_CR15","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/net.3230260202","volume":"26","author":"M Grigoriadis","year":"1995","unstructured":"Grigoriadis M, Khachiyan LG (1995a) An exponential-function reduction method for block-angular convex programs. Networks 26(1.2):59\u201368","journal-title":"Networks"},{"issue":"2","key":"9225_CR16","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0167-6377(95)00032-0","volume":"18","author":"M Grigoriadis","year":"1995","unstructured":"Grigoriadis M, Khachiyan LG (1995b) A sublinear-time randomized approximation algorithm for matrix games. Oper Res Lett 18(2):53\u201358","journal-title":"Oper Res Lett"},{"key":"9225_CR17","first-page":"477","volume":"75","author":"M Grigoriadis","year":"1996","unstructured":"Grigoriadis M, Khachiyan LG (1996a) Approximate minimum-cost multicommodity flows in o(\u03b5 \u22122 knm) time. Math Program 75:477\u2013482","journal-title":"Math Program"},{"key":"9225_CR18","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1287\/moor.21.2.321","volume":"21","author":"M Grigoriadis","year":"1996","unstructured":"Grigoriadis M, Khachiyan LG (1996b) Coordination complexity of parallel price-directive decomposition. Math Oper Res 21:321\u2013340","journal-title":"Math Oper Res"},{"key":"9225_CR19","doi-asserted-by":"crossref","unstructured":"Guruswami V, Khanna S, Rajaraman R, Shepherd B, Yannakakis M (1999) 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\u00a019\u201328","DOI":"10.1145\/301250.301262"},{"issue":"3","key":"9225_CR20","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1137\/S0097539792241175","volume":"23","author":"P Klein","year":"1994","unstructured":"Klein P, Plotkin SA, Shmoys DB, Tardos E (1994) Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM J Comput 23(3):466\u2013487","journal-title":"SIAM J Comput"},{"key":"9225_CR21","unstructured":"Kleinberg JM (May 1996) Approximation algorithms for disjoint path problems. PhD thesis, Massachusetts Institute of Technology"},{"key":"9225_CR22","volume-title":"Handbook of approximation algorithms and metaheuristics","author":"SG Kolliopoulos","year":"2007","unstructured":"Kolliopoulos SG (2007) Edge-disjoint paths and unsplittable flow. In: Gonzalez TF (ed) Handbook of approximation algorithms and metaheuristics. Chapman & Hall\/CRC, London"},{"key":"9225_CR23","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/s10107-002-0370-6","volume":"99","author":"SG Kolliopoulos","year":"2004","unstructured":"Kolliopoulos SG, Stein C (2004) Approximating disjoint-path problems using packing integer programs. Math Program Ser A 99:63\u201387","journal-title":"Math Program Ser A"},{"key":"9225_CR24","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1287\/mnsc.18.7.401","volume":"18","author":"EL Lawler","year":"1972","unstructured":"Lawler EL (1972) A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Manag Sci 18:401\u2013405","journal-title":"Manag Sci"},{"issue":"2","key":"9225_CR25","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1006\/jcss.1995.1020","volume":"50","author":"T Leighton","year":"1995","unstructured":"Leighton T, Makedon F, Plotkin SA, Stein C, Tardos E (1995) Fast approximation algorithms for multicommodity flow problems. J Comput Syst Sci 50(2):228\u2013243","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"9225_CR26","doi-asserted-by":"crossref","first-page":"329","DOI":"10.2307\/3027286","volume":"14","author":"JF Lucas","year":"1983","unstructured":"Lucas JF (1983) Paths and Pascal numbers. Two-Year College Math J 14(4):329\u2013341","journal-title":"Two-Year College Math J"},{"key":"9225_CR27","unstructured":"Martens M (2007) Path-constrained network flows. PhD thesis, Universit\u00e4t Dortmund"},{"issue":"2","key":"9225_CR28","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1002\/net.20121","volume":"48","author":"M Martens","year":"2006","unstructured":"Martens M, Skutella M (2006) Flows on few paths: Algorithms and lower bounds. Networks 48(2):68\u201376","journal-title":"Networks"},{"key":"9225_CR29","volume-title":"Computational complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou CH (1994) Computational complexity. Addison-Wesley, Reading"},{"key":"9225_CR30","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"SA Plotkin","year":"1995","unstructured":"Plotkin SA, Shmoys DB, Tardos E (1995) Fast approximation algorithms for fractional packing and covering problems. Math Oper Res 20:257\u2013301","journal-title":"Math Oper Res"},{"key":"9225_CR31","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1987","unstructured":"Raghavan P, Thompson CD (1987) Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7:365\u2013374","journal-title":"Combinatorica"},{"key":"9225_CR32","unstructured":"Roditty L (2007) On the k-simple shortest paths problem in weighted directed graphs. In: Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms, pp\u00a0920\u2013928"},{"key":"9225_CR33","volume-title":"Combinatorial optimization. Polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization. Polyhedra and efficiency. Springer, Berlin"},{"key":"9225_CR34","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1145\/77600.77620","volume":"37","author":"F Shahrokhi","year":"1990","unstructured":"Shahrokhi F, Matula DW (1990) The maximum concurrent flow problem. J ACM 37:318\u2013334","journal-title":"J ACM"},{"issue":"1","key":"9225_CR35","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1006\/jcta.1996.0046","volume":"74","author":"RP Stanley","year":"1996","unstructured":"Stanley RP (1996) A matrix for counting paths in acyclic digraphs. J Comb Theory Ser A 74(1):169\u2013172","journal-title":"J Comb Theory Ser A"},{"issue":"3","key":"9225_CR36","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J Comput 8(3):410\u2013421","journal-title":"SIAM J Comput"},{"issue":"11","key":"9225_CR37","doi-asserted-by":"crossref","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","volume":"17","author":"JY Yen","year":"1971","unstructured":"Yen JY (1971) Finding the k shortest loopless paths in a network. Manag Sci 17(11):712\u2013716","journal-title":"Manag Sci"},{"key":"9225_CR38","doi-asserted-by":"crossref","unstructured":"Young NE (2001) Sequential and parallel algorithms for mixed packing and covering. In: IEEE symposium on foundations of computer science, pp\u00a0538\u2013546","DOI":"10.1109\/SFCS.2001.959930"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9225-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9225-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9225-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:14Z","timestamp":1559276294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9225-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,21]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9225"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9225-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,21]]}}}