{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:17:39Z","timestamp":1725520659879},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540767954"},{"type":"electronic","value":"9783540767961"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-76796-1_5","type":"book-chapter","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T07:24:04Z","timestamp":1225956244000},"page":"69-85","source":"Crossref","is-referenced-by-count":6,"title":["Strongly Polynomial Algorithm for the Intersection of\u00a0a\u00a0Line with a Polymatroid"],"prefix":"10.1007","author":[{"given":"Jean","family":"Fonlupt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandre","family":"Skoda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"5_CR1","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1287\/moor.10.3.367","volume":"10","author":"R.E. Bixby","year":"1985","unstructured":"Bixby, R.E., Cunningham, W.H., Topkis, D.M.: The partial order of a polymatroid extreme point. Math. Oper. Res. 10(3), 367\u2013378 (1985)","journal-title":"Math. Oper. Res."},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0020-0190(94)90013-2","volume":"49","author":"E. Cheng","year":"1994","unstructured":"Cheng, E., Cunningham, W.H.: A faster algorithm for computing the strength of a network. Inf. Process. Lett. 49, 209\u2013212 (1994)","journal-title":"Inf. Process. Lett."},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0095-8956(84)90023-6","volume":"36","author":"W.H. Cunningham","year":"1984","unstructured":"Cunningham, W.H.: Testing membership in matroid polyhedra. J. Comb. Theory, Ser. B 36, 161\u2013188 (1984)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"3","key":"5_CR4","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/3828.3829","volume":"32","author":"W.H. Cunningham","year":"1985","unstructured":"Cunningham, W.H.: Optimal attack and reinforcement of a network. J. Assoc. Comput. Mach. 32(3), 549\u2013561 (1985a)","journal-title":"J. Assoc. Comput. Mach."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF02579361","volume":"5","author":"W.H. Cunningham","year":"1985","unstructured":"Cunningham, W.H.: On submodular function minimization. Combinatorica 5, 185\u2013192 (1985b)","journal-title":"Combinatorica"},{"key":"5_CR6","first-page":"69","volume-title":"Combinatorial Structures and Their Applications, Proceedings of the Calgary International Conference","author":"J. Edmonds","year":"1970","unstructured":"Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Combinatorial Structures and Their Applications, Proceedings of the Calgary International Conference, pp. 69\u201387. Gordon and Breach, New York (1970)"},{"key":"5_CR7","first-page":"1","volume":"64","author":"L. Fleischer","year":"2000","unstructured":"Fleischer, L.: Recent progress in submodular function minimization. Optima 64, 1\u201311 (2000)","journal-title":"Optima"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Fleischer, L., Iwata, S.: Improved algorithms for submodular function minimization and submodular flow. In: STOC \u201900: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 107\u2013116 (2000)","DOI":"10.1145\/335305.335318"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1287\/moor.5.2.186","volume":"5","author":"S. Fujishige","year":"1980","unstructured":"Fujishige, S.: Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 5, 186\u2013196 (1980)","journal-title":"Math. Oper. Res."},{"key":"5_CR10","series-title":"Annals of Discrete Mathematics","volume-title":"Submodular Functions and Optimization","author":"S. Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics, vol.\u00a058. Elsevier, Amsterdam (2005)"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/S0097539701397813","volume":"32","author":"S. Iwata","year":"2003","unstructured":"Iwata, S.: A faster scaling algorithm for minimizing submodular functions. SIAM J. Comput. 32, 833\u2013840 (2003)","journal-title":"SIAM J. Comput."},{"key":"5_CR13","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S. Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial time algorithm for minimizing submodular functions. J. Assoc. Comput. Mach. 48, 761\u2013777 (2001)","journal-title":"J. Assoc. Comput. Mach."},{"key":"5_CR14","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"B. Korte","year":"2008","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 4th edn. Algorithms and Combinatorics, vol.\u00a021. Springer, Berlin (2008)","edition":"4"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01585506","volume":"7","author":"N. Megiddo","year":"1974","unstructured":"Megiddo, N.: Optimal flows in networks with multiple sources and sinks. Math. Program. 7, 97\u2013107 (1974)","journal-title":"Math. Program."},{"key":"5_CR16","unstructured":"Nagano, K.: A strongly polynomial algorithm for line search in submodular polyhedra. Mathematical engineering technical report, Department of Mathematical Informatics, The University of Tokyo (2004)"},{"key":"5_CR17","unstructured":"Nagano, K.: A faster parametric submodular function minimization algorithm and applications. Mathematical engineering technical report, Department of Mathematical Informatics, The University of Tokyo (2007)"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: A faster strongly polynomial time algorithm for submodular function minimization. In: Proc of IPCO, pp. 240\u2013251 (2007)","DOI":"10.1007\/978-3-540-72792-7_19"},{"issue":"2","key":"5_CR19","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A. Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory, Ser. B 80(2), 346\u2013355 (2000)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"5_CR20","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"5_CR21","unstructured":"Skoda, A.: Force d\u2019un graphe, multicoupes et fonctions sous-modulaires: aspects structurels et algorithmiques. PhD thesis, Universit\u00e9 Pierre et Marie Curie, Paris 6 (2007)"},{"issue":"2","key":"5_CR22","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1016\/S0095-8956(02)00047-3","volume":"88","author":"J. Vygen","year":"2003","unstructured":"Vygen, J.: A note on Schrijver\u2019s submodular function minimization algorithm. J. Comb. Theory, Ser. B 88(2), 399\u2013402 (2003)","journal-title":"J. Comb. Theory, Ser. B"}],"container-title":["Research Trends in Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-76796-1_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:39:02Z","timestamp":1619519942000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-76796-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540767954","9783540767961"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-76796-1_5","relation":{},"subject":[]}}