{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T18:03:56Z","timestamp":1775671436138,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642688768","type":"print"},{"value":"9783642688744","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1983]]},"DOI":"10.1007\/978-3-642-68874-4_10","type":"book-chapter","created":{"date-parts":[[2011,10,25]],"date-time":"2011-10-25T13:36:08Z","timestamp":1319549768000},"page":"235-257","source":"Crossref","is-referenced-by-count":478,"title":["Submodular functions and convexity"],"prefix":"10.1007","author":[{"given":"L.","family":"Lov\u00e1sz","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1090\/S0002-9947-1971-0286689-5","volume":"158","author":"M Aigner","year":"1971","unstructured":"M. Aigner, T. A. Dowling (1971), Matching theory for combinatorial geometries, Trans. Amer. Math. Soc. 158, 231\u2013245.","journal-title":"Trans. Amer. Math. Soc."},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"131","DOI":"10.5802\/aif.53","volume":"5","author":"L Choquet","year":"1955","unstructured":"L. Choquet (1955), Theory of capacities, Ann. Inst. Fournier Grenoble 5, 131\u2013295.","journal-title":"Ann. Inst. Fournier Grenoble"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"H. Crapo (1965), Single-element extensions of matroids, J. Res. Nat. Bur. Stand. 69 B, 55\u201365.","DOI":"10.6028\/jres.069B.003"},{"key":"10_CR4","first-page":"26","volume":"1","author":"H Crapo","year":"1979","unstructured":"H. Crapo (1979), Structural rigidity, Structural Topology 1, 26\u201345.","journal-title":"Structural Topology"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1215\/S0012-7094-44-01150-6","volume":"11","author":"RP Dilworth","year":"1944","unstructured":"R. P. Dilworth (1944), Dependence relations in a semimodular lattice, Duke Math. J. 11, 575\u2013586.","journal-title":"Duke Math. J."},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1093\/qmath\/27.3.339","volume":"27","author":"FDJ Dunstan","year":"1976","unstructured":"F. D. J. Dunstan (1976), Matroids and submodular functions, Quart. J. Math. Oxford 27, 339\u2013348.","journal-title":"Quart. J. Math. Oxford"},{"key":"10_CR7","first-page":"69","volume-title":"Combinatorial Structures and their Applications","author":"J Edmonds","year":"1970","unstructured":"J. Edmonds (1970), Submodular functions, matroids, and certain polyhedra, in: Combinatorial Structures and their Applications (eds. R. Guy, H. Hanani, N. Sauer, J. Sch\u00f6nheim) Gordon and Breach, 69\u201387."},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"J. Edmonds, D. R. Fulkerson (1965), Transversals and matroid partition, J. Res. Nat. Bur. Stand. 69 B, 147\u2013153.","DOI":"10.6028\/jres.069B.016"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0167-5060(08)70734-9","volume":"1","author":"J Edmonds","year":"1977","unstructured":"J. Edmonds, R. Giles (1977), A min-max relation on submodular functions on graphs, Annals of Discrete Math. 1, 185\u2013204.","journal-title":"Annals of Discrete Math"},{"key":"10_CR10","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"M. L. Fisher, G. L. Nemhauser, L. A. Wolsey (1978), Analysis of approximations for maximizing a submodular setfunction II, Math. Prog. Study 8, 73\u201387.","journal-title":"Math. Prog. Study"},{"key":"10_CR11","first-page":"97","volume":"16","author":"A Frank","year":"1982","unstructured":"A. Frank (1982), An algorithm for submodular functions on graphs, Annals of Discrete Math. 16, 97\u2013120.","journal-title":"Annals of Discrete Math"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0095-8956(80)90071-4","volume":"28","author":"A Frank","year":"1980","unstructured":"A. Frank (1980), On the orientation of graphs, J. Comb. Theory B28, 251\u2013261.","journal-title":"J. Comb. Theory"},{"key":"10_CR13","first-page":"63","volume":"41","author":"A Frank","year":"1979","unstructured":"A. Frank (1979), Kernel systems of directed graphs, Acta Sci. Math. Univ. Szeged 41, 63\u201376.","journal-title":"Acta Sci. Math. Univ. Szeged"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/BF02579175","volume":"1","author":"H Gr\u00f6flin","year":"1981","unstructured":"H. Gr\u00f6flin, A. J. Hoffman (1981), On matroid intersections, Combinatorica 1, 43\u201347.","journal-title":"Combinatorica"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, A. Schrijver (1981), The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1, 169\u2013197.","journal-title":"Combinatorica"},{"key":"10_CR16","volume-title":"Bonn","author":"PM Jensen","year":"1978","unstructured":"P. M. Jensen, B. Korte (1978), Complexity of matroid property algorithms, Rept. No. 7124-OR, Inst. \u00d6kon. Oper. Res. Univ. Bonn."},{"key":"10_CR17","first-page":"214","volume-title":"Hypergraph Seminar","author":"T Helgason","year":"1974","unstructured":"T. Helgason (1974), Aspects of the theory of hypermatroids, in: Hypergraph Seminar (eds. C. Berge, D. K. Ray-Chaudhuri), Lecture Notes in Math. 411, Springer, 191\u2013 214."},{"issue":"3","key":"10_CR18","first-page":"24","volume":"13","author":"DB Iudin","year":"1976","unstructured":"D. B. Iudin, A. S. Nemirovskii (1976), Informational complexity and effective methods of solution for convex extremal problems, Ekon. i Mat. Met. 12, 357\u2013369; Matekon 13 (3), 24\u201345.","journal-title":"Matekon"},{"key":"10_CR19","unstructured":"E. L. Lawler, C. U. Martell (1980), Computing maximal \u201cpolymatroidal\u201d network flows, Res. Rep. UCB\/ERL M80 \/52."},{"key":"10_CR20","unstructured":"E. L. Lawler, Po Tong (1982), Lecture at the Conference on Combinatorics and Graph Theory, Univ. of Waterloo."},{"key":"10_CR21","first-page":"45","volume-title":"Combinatorial Surveys","author":"L Lov\u00e1sz","year":"1977","unstructured":"L. Lov\u00e1sz (1977), Flats in matroids and geometric graphs, in: Combinatorial Surveys, (ed. P. Cameron ), Acad. Press, 45\u201386."},{"key":"10_CR22","first-page":"495","volume-title":"Algebraic Methods in Graph Theory","author":"L Lov\u00e1sz","year":"1981","unstructured":"L. Lov\u00e1sz (1981), The matroid matching problem, in: Algebraic Methods in Graph Theory (eds. L. Lovasz, V. T. Sos ), North-Holland, 495\u2013517."},{"key":"10_CR23","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/0603009","volume":"3","author":"L Lov\u00e1sz","year":"1982","unstructured":"L. Lov\u00e1sz, Y. Yemini (1982), On generic rigidity in the plane, SIAM J. on Alg. Discr. Meth. 3, 91\u201399.","journal-title":"SIAM J. on Alg. Discr. Meth."},{"key":"10_CR24","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1017\/S0305004100051677","volume":"78","author":"CJH McDiarmid","year":"1975","unstructured":"C. J. H. McDiarmid (1975), Rado\u2019s Theorem for polymatroids, Math. Proc. Cambridge Phil. Soc. 78, 263\u2013281.","journal-title":"Math. Proc. Cambridge Phil. Soc."},{"key":"10_CR25","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/978-94-010-1220-1_9","volume-title":"Higher Combinatorics","author":"JH Mason","year":"1977","unstructured":"J. H. Mason (1977), Matroids as the study of geometrical configurations, in: Higher Combinatorics (ed. M. Aigner) Reidel, 133\u2013176."},{"key":"10_CR26","first-page":"519","volume-title":"Algebraic Methods in Graph Theory","author":"JH Mason","year":"1981","unstructured":"J. H. Mason (1981), Glueing matroids together: a study of Dilworth truncations and matroid analogues of exterior and symmetric powers, in: Algebraic Methods in Graph Theory (eds. L. Lovasz, V. T. Sos ), North-Holland, 519\u2013561."},{"key":"10_CR27","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1090\/S0002-9947-1978-0491269-9","volume":"238","author":"HQ Nguyen","year":"1978","unstructured":"H. Q. Nguyen (1978), Semimodular functions and combinatorial geometries, Trans. AMS 238, 355\u2013383.","journal-title":"Trans. AMS"},{"key":"10_CR28","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1215\/S0012-7094-55-02268-7","volume":"22","author":"O Ore","year":"1955","unstructured":"O. Ore (1955), Graphs and matching theorems, Duke Math. J. 22, 625\u2013639.","journal-title":"Duke Math J"},{"key":"10_CR29","unstructured":"D. Welsh (1976), Matroid Theory, Academic Press."}],"container-title":["Mathematical Programming The State of the Art"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-68874-4_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T17:31:13Z","timestamp":1606239073000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-68874-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983]]},"ISBN":["9783642688768","9783642688744"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-68874-4_10","relation":{},"subject":[],"published":{"date-parts":[[1983]]}}}