{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:32:39Z","timestamp":1759667559823},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1994,3,1]],"date-time":"1994-03-01T00:00:00Z","timestamp":762480000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,3]]},"DOI":"10.1007\/bf01240739","type":"journal-article","created":{"date-parts":[[2005,2,26]],"date-time":"2005-02-26T03:15:44Z","timestamp":1109387744000},"page":"320-340","source":"Crossref","is-referenced-by-count":8,"title":["Algorithms and complexity analysis for some flow problems"],"prefix":"10.1007","volume":"11","author":[{"given":"Edith","family":"Cohen","sequence":"first","affiliation":[]},{"given":"Nimrod","family":"Megiddo","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","volume-title":"Flow Algorithms","author":"G. M. Adel'son-Velskii","year":"1975","unstructured":"G. M. Adel'son-Velskii, E. A. Dinic, and A. V. Karzanov.Flow Algorithms. Science, Moscow, 1975. In Russian."},{"key":"CR2","volume-title":"Programming, Games and Transportation Networks","author":"C. Berge","year":"1965","unstructured":"C. Berge and A. Ghouila-Houri.Programming, Games and Transportation Networks. Wiley, New York, 1965."},{"key":"CR3","volume-title":"Ph.D. thesis","author":"P. J. Carstensen","year":"1983","unstructured":"P. J. Carstensen. The Complexity of Some Problems in Parametric, Linear, and Combinatorial Programming. Ph.D. thesis, Department of Mathematics, University of Michigan, Ann Arbor, MI, 1983."},{"key":"CR4","volume-title":"Ph.D. thesis","author":"E. Cohen","year":"1991","unstructured":"E. Cohen. Combinatorial Algorithms for Optimization Problems. Ph.D. thesis, Department of Computer Science, Stanford University, Stanford, CA, 1991."},{"key":"CR5","first-page":"523","volume-title":"Proc. 21st Annual ACM Symposium on Theory of Computing","author":"E. Cohen","year":"1989","unstructured":"E. Cohen and N. Megiddo. Strongly polynomial and NC algorithms for detecting cycles in dynamic graphs.Proc. 21st Annual ACM Symposium on Theory of Computing, pp. 523?534. ACM, New York, 1989."},{"key":"CR6","first-page":"95120","volume-title":"Technical Report RJ 7656 (71103)","author":"E. Cohen","year":"1990","unstructured":"E. Cohen and N. Megiddo. Maximizing Concave Functions in Fixed Dimension. Technical Report RJ 7656 (71103), IBM Almaden Research Center, San Jose, CA 95120?6099, August 1990."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"E. Cohen and N. Megiddo. Strongly polynomial time and NC algorithms for detecting cycles in periodic graphs.J. Assoc. Comput. Mach. To appear.","DOI":"10.1145\/153724.153727"},{"key":"CR8","first-page":"1277","volume":"11","author":"E. A. Dinic","year":"1970","unstructured":"E. A. Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation.Soviet Math. Dokl., 11:1277?1280, 1970.","journal-title":"Soviet Math. Dokl."},{"issue":"2","key":"CR9","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0020-0190(79)90152-2","volume":"8","author":"D. P. Dobkin","year":"1978","unstructured":"D. P. Dobkin, R. J. Lipton, and S. P. Reiss. Linear programming is log-space hard for P.Inform. Process. Lett., 8(2):96?97, 1978.","journal-title":"Inform. Process. Lett."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(80)90031-6","volume":"11","author":"D. P. Dobkin","year":"1980","unstructured":"D. P. Dobkin and S. P. Reiss. The complexity of linear programming.Theoret. Comput. Sci., 11:1?18, 1980.","journal-title":"Theoret. Comput. Sci."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems.J. Assoc. Comput. Mach., 19:248?264, 1972.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR12","volume-title":"Flows in Networks","author":"L. R. Ford Jr.","year":"1962","unstructured":"L. R. Ford, Jr., and D. R. Fulkerson.Flows in Networks. Princeton University Press, Princeton, NJ, 1962."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G. Gallo","year":"1989","unstructured":"G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A fast parametric maximum flow algorithm and applications.SIAM J. Comput., 18:30?55, 1989.","journal-title":"SIAM J. Comput."},{"key":"CR14","first-page":"156","volume-title":"Proc. 2nd International Conference on Operations Research, London","author":"A. Ghouila-Houri","year":"1960","unstructured":"A. Ghouila-Houri. Recherche du flot maximum dans certains r\u00e9seaux lorsqu'on impose une condition de bouclage.Proc. 2nd International Conference on Operations Research, London, p. 156. American Mathematical Society, Providence, RI, 1960."},{"key":"CR15","first-page":"457","volume":"250","author":"A. Ghouila-Houri","year":"1960","unstructured":"A. Ghouila-Houri. Une g\u00e9n\u00e9ralisation de l'algorithme de Ford-Fulkerson.C. R. Acad. Sci. Paris, 250:457, 1960.","journal-title":"C. R. Acad. Sci. Paris"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg, \u00c9. Tardos, and R. E. Tarjan. Network Flow Algorithms. Technical Report STAN-CS-89-1252, Stanford University, 1989.","DOI":"10.21236\/ADA214689"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF01442864","volume":"6","author":"P. Gordan","year":"1873","unstructured":"P. Gordan. \u00dcber die aufl\u00f6sung linearer gleichungen mit reelen coefficienten.Math. Ann., 6:23?28, 1873.","journal-title":"Math. Ann."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1145\/2402.322391","volume":"30","author":"D. Gusfield","year":"1983","unstructured":"D. Gusfield. Parametric combinatorial computing and a problem of program module distribution.J. Assoc. Comput. Mach., 30:551?563, 1983.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1007\/BF01580250","volume":"6","author":"A. J. Hoffman","year":"1974","unstructured":"A. J. Hoffman. A generalization of max-flow min-cut.Math. Programming, 6:352?359, 1974.","journal-title":"Math. Programming"},{"issue":"4","key":"CR20","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/322092.322100","volume":"25","author":"A. Itai","year":"1978","unstructured":"A. Itai. Two-commodity flow.J. Assoc. Comput. Mach., 25(4):596?611, 1978.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR21","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. L. Lawler","year":"1976","unstructured":"E. L. Lawler.Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston, New York, 1976."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1090\/S0002-9904-1977-14298-5","volume":"83","author":"N. Megiddo","year":"1977","unstructured":"N. Megiddo. A good algorithm for lexicographically optimal flows in multi-terminal networks.Bull. Amer. Math. Soc., 83:407?409, 1977.","journal-title":"Bull. Amer. Math. Soc."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms.J. Assoc. Comput. Mach., 30:337?341, 1983.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1137\/0212022","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo. Towards a genuinely polynomial algorithm for linear programming.SIAM J. Comput., 12:347?353, 1983.","journal-title":"SIAM J. Comput."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"N. Megiddo. Linear programming in linear time when the dimension is fixed.J. Assoc. Comput. Mach., 31:114?127, 1984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR26","first-page":"377","volume-title":"Proc. 1st ACM-SIAM Symposium on Discrete Algorithms","author":"C. H. Norton","year":"1990","unstructured":"C. H. Norton, S. A. Plotkin, and \u00c9. Tardos. Using separation algorithms in fixed dimension.Proc. 1st ACM-SIAM Symposium on Discrete Algorithms, pp. 377?387. ACM-SIAM, New York\/Philadelphia, 1990."},{"issue":"3","key":"CR27","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF02579369","volume":"5","author":"\u00c9. Tardos","year":"1985","unstructured":"\u00c9. Tardos. A strongly polynomial minimum cost circulation algorithm.Combinatorica, 5(3):247?255, 1985.","journal-title":"Combinatorica"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"E. Tardos. A strongly polynomial algorithm to solve combinatorial linear programs.Oper. Res., 34:250?256, 1986.","journal-title":"Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01240739.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01240739\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01240739","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T00:17:37Z","timestamp":1586132257000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01240739"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,3]]}},"alternative-id":["BF01240739"],"URL":"https:\/\/doi.org\/10.1007\/bf01240739","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]}}}