{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T07:11:50Z","timestamp":1775286710231,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1981,6,1]],"date-time":"1981-06-01T00:00:00Z","timestamp":360201600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1981,6]]},"DOI":"10.1007\/bf02579273","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T22:16:08Z","timestamp":1174601768000},"page":"169-197","source":"Crossref","is-referenced-by-count":1293,"title":["The ellipsoid method and its consequences in combinatorial optimization"],"prefix":"10.1007","volume":"1","author":[{"given":"M.","family":"Gr\u00f6tschel","sequence":"first","affiliation":[]},{"given":"L.","family":"Lov\u00e1sz","sequence":"additional","affiliation":[]},{"given":"A.","family":"Schrijver","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02579273_CR1","first-page":"1396","volume":"4","author":"Chu Yoeng-jin","year":"1965","unstructured":"Chu Yoeng-jin andLiu Tseng-hung, On the shortest arborescence of a directed graph,Scientia Sinica 4 (1965) 1396\u20131400.","journal-title":"Scientia Sinica"},{"key":"BF02579273_CR2","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra, A note on two problems in connexion with graphs,Numer. Math. 1 (1959) 269\u2013271.","journal-title":"Numer. Math."},{"key":"BF02579273_CR3","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices,J. Res. Nat. Bur. Standards Sect. B 69 (1965) 125\u2013130.","journal-title":"J. Res. Nat. Bur. Standards Sect. B"},{"key":"BF02579273_CR4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71","author":"J. Edmonds","year":"1967","unstructured":"J. Edmonds, Optimum branchings,J. Res. Nat. Bur. Standards Sect. B 71 (1967) 233\u2013240.","journal-title":"J. Res. Nat. Bur. Standards Sect. B"},{"key":"BF02579273_CR5","first-page":"69","volume-title":"Combinatorial structures and their applications","author":"J. Edmonds","year":"1970","unstructured":"J. Edmonds, Submodular functions, matroids, and certain polyhedra, in:Combinatorial structures and their applications, Proc. Intern. Conf. Calgary, Alb., 1969 (R. Guy, H. Hanani, N. Sauer, and J. Sch\u00f6nheim, eds.), Gordon and Breach, New York, 1970, 69\u201387."},{"key":"BF02579273_CR6","first-page":"89","volume-title":"Combinatorial structures and their applications","author":"J. Edmonds","year":"1970","unstructured":"J. Edmonds andE. L. Johnson, Matching: a well-solved class of integer linear programs, \u2014ibid. 89\u201392."},{"key":"BF02579273_CR7","first-page":"91","volume-title":"Combinatorial algorithms","author":"J. Edmonds","year":"1973","unstructured":"J. Edmonds, Edge-disjoint branchings, in:Combinatorial algorithms, Courant Comp. Sci. Symp. Monterey, Ca., 1972 (R. Rustin, ed.), Acad. Press, New York, 1973, 91\u201396."},{"key":"BF02579273_CR8","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0167-5060(08)70817-3","volume":"4","author":"J. Edmonds","year":"1979","unstructured":"J. Edmonds, Matroid intersection,Annals of Discrete Math. 4 (1979) 39\u201349.","journal-title":"Annals of Discrete Math."},{"key":"BF02579273_CR9","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0167-5060(08)70734-9","volume":"1","author":"J. Edmonds","year":"1977","unstructured":"J. Edmonds andR. Giles, A min-max relation for submodular functions on graphs,Annals of Discrete Math. 1 (1977) 185\u2013204.","journal-title":"Annals of Discrete Math."},{"key":"BF02579273_CR10","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J. Edmonds","year":"1973","unstructured":"J. Edmonds andE. L. Johnson, Matching, Euler tours and the Chinese postman,Math. Programming 5 (1973) 88\u2013124.","journal-title":"Math. Programming"},{"key":"BF02579273_CR11","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L. R. Ford","year":"1956","unstructured":"L. R. Ford andD. R. Fulkerson, Maximum flow through a network,Canad. J. Math. 8 (1956) 399\u2013404.","journal-title":"Canad. J. Math."},{"key":"BF02579273_CR12","volume-title":"Flows in networks","author":"L. R. Ford","year":"1962","unstructured":"L. R. Ford andD. R. Fulkerson,Flows in networks, Princeton Univ. Press, Princeton, N. J., 1962."},{"key":"BF02579273_CR13","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0095-8956(80)90071-4","volume":"28","author":"A. Frank","year":"1980","unstructured":"A. Frank, On the orientations of graphs,J. Combinatorial Theory (B) 28 (1980) 251\u2013260.","journal-title":"J. Combinatorial Theory (B)"},{"key":"BF02579273_CR14","first-page":"63","volume":"41","author":"A. Frank","year":"1979","unstructured":"A. Frank, Kernel systems of directed graphs,Acta Sci. Math. (Szeged)41 (1979) 63\u201376.","journal-title":"Acta Sci. Math. (Szeged)"},{"issue":"2","key":"BF02579273_CR15","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02579270","volume":"1","author":"A. Frank","year":"1981","unstructured":"A. Frank, How to make a digraph strongly connected,Combinatorica 1 (2) (1981) 145\u2013153.","journal-title":"Combinatorica"},{"key":"BF02579273_CR16","first-page":"303","volume-title":"Mathematics of the decision sciences, Part I","author":"D. R. Fulkerson","year":"1968","unstructured":"D. R. Fulkerson, Networks, frames, and blocking systems, in:Mathematics of the decision sciences, Part I (G. B. Dantzig and A. F. Veinott, eds.), Amer. Math. Soc., Providence, R. I., 1968, 303\u2013334."},{"key":"BF02579273_CR17","first-page":"93","volume-title":"Graph theory and its applications","author":"D. R. Fulkerson","year":"1970","unstructured":"D. R. Fulkerson, Blocking polyhedra, in:Graph theory and its applications, Proc. adv. Seminar Madison, Wis., 1969 (B. Harris, ed.), Acad. Press, New York, 1970, 93\u2013112."},{"key":"BF02579273_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01580218","volume":"6","author":"D. R. Fulkerson","year":"1974","unstructured":"D. R. Fulkerson, Packing rooted directed cuts in a weighted directed graph,Math. Programming 6 (1974) 1\u201313.","journal-title":"Math. Programming"},{"key":"BF02579273_CR19","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BFb0120921","volume":"14","author":"P. G\u00e1cs","year":"1981","unstructured":"P. G\u00e1cs andL. Lov\u00e1sz, Khachiyan\u2019s algorithm for linear programming,Math. Programming Studies 14 (1981) 61\u201368.","journal-title":"Math. Programming Studies"},{"key":"BF02579273_CR20","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey andD. S. Johnson,Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979."},{"key":"BF02579273_CR21","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1090\/psapm\/010\/0114759","volume-title":"Combinatorial analysis","author":"A. J. Hoffman","year":"1960","unstructured":"A. J. Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, in:Combinatorial analysis, Proc. 10th Symp. on Appl. Math. Columbia Univ., 1958 (R. E. Bellman and M. Hall, Jr, eds.), Amer. Math. Soc., Providence, R. I., 1960, 113\u2013127."},{"key":"BF02579273_CR22","unstructured":"I. Holyer, The NP-completeness of edge-colouring,SIAM J. Comp., to appear."},{"key":"BF02579273_CR23","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/opre.11.3.344","volume":"11","author":"T. C. Hu","year":"1963","unstructured":"T. C. Hu, Multicommodity network flows,Operations Res. 11 (1963) 344\u2013360.","journal-title":"Operations Res."},{"key":"BF02579273_CR24","first-page":"108","volume":"4","author":"T. C. Hu","year":"1973","unstructured":"T. C. Hu, Two-commodity cut-packing problem,Discrete Math. 4 (1973) 108\u2013109.","journal-title":"Discrete Math."},{"key":"BF02579273_CR25","unstructured":"A. V. Karzanov, On the minimal number of arcs of a digraph meeting all its directed cutsets,to appear."},{"key":"BF02579273_CR26","first-page":"1093","volume":"244","author":"L. G. Khachiyan","year":"1979","unstructured":"L. G. Khachiyan, A polynomial algorithm in linear programming,Doklady Akademii Nauk SSSR 244 (1979) 1093\u20131096 (English translation:Soviet Math. Dokl. 20, 191\u2013194).","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"BF02579273_CR27","first-page":"233","volume-title":"Combinatorial structures and their applications","author":"E. L. Lawler","year":"1970","unstructured":"E. L. Lawler, Optimal matroid intersections, in:Combinatorial structures and their applications, Proc. Intern. Conf. Calgary, Alb., 1969 (R. Guy, H. Hanani, N. Sauer, and J. Sch\u00f6nheim, eds.), Gordon and Breach, New York, 1970, 233\u2013235."},{"key":"BF02579273_CR28","volume-title":"Combinatorial optimization: networks and matroids","author":"E. L. Lawler","year":"1976","unstructured":"E. L. Lawler,Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, New York, 1976."},{"key":"BF02579273_CR29","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L. Lov\u00e1sz","year":"1972","unstructured":"L. Lov\u00e1sz, Normal hypergraphs and the perfect graph conjecture,Discrete Math. 2 (1972) 253\u2013267.","journal-title":"Discrete Math."},{"key":"BF02579273_CR30","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF01902352","volume":"26","author":"L. Lov\u00e1sz","year":"1975","unstructured":"L. Lov\u00e1sz, 2-Matchings and 2-covers of hypergraphs,Acta Math. Acad. Sci. Hungar. 26 (1975) 433\u2013444.","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"BF02579273_CR31","unstructured":"L. Lov\u00e1sz, The matroid matching problem,Proc. Conf. Algebraic Methods in Graph Theory (Szeged, 1978), to appear."},{"key":"BF02579273_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"L. Lov\u00e1sz, On the Shannon capacity of a graph,IEEE Trans. on Information Theory 25 (1979) 1\u20137.","journal-title":"IEEE Trans. on Information Theory"},{"key":"BF02579273_CR33","unstructured":"L. Lov\u00e1sz, Perfect graphs, in:More selected topics in graph theory (L. W. Beineke and R. J. Wilson, eds), to appear"},{"key":"BF02579273_CR34","volume-title":"A minimax equality for directed graphs","author":"C. L. Lucchesi","year":"1976","unstructured":"C. L. Lucchesi, A minimax equality for directed graphs,Doctoral Thesis, Univ. Waterloo, Waterloo, Ont., 1976."},{"key":"BF02579273_CR35","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1112\/jlms\/s2-17.3.369","volume":"17","author":"C. L. Lucchesi","year":"1978","unstructured":"C. L. Lucchesi andD. H. Younger, A minimax relation for directed graphs,J. London Math. Soc. (2) 17 (1978) 369\u2013374.","journal-title":"J. London Math. Soc. (2)"},{"key":"BF02579273_CR36","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"G. J. Minty","year":"1980","unstructured":"G. J. Minty, On maximal independent sets of vertices in claw-free graphs,J. Combinatorial Theory (B),28 (1980) 284\u2013304.","journal-title":"J. Combinatorial Theory (B)"},{"key":"BF02579273_CR37","doi-asserted-by":"crossref","first-page":"393","DOI":"10.4153\/CJM-1954-038-x","volume":"6","author":"T. S. Motzkin","year":"1954","unstructured":"T. S. Motzkin andI. J. Schoenberg, The relaxation method for linear inequalities,Canad. J. Math. 6 (1954) 393\u2013404.","journal-title":"Canad. J. Math."},{"key":"BF02579273_CR38","unstructured":"H. Okamura andP. D. Seymour, Multicommodity flows in planar graphs,J. Combinatorial Theory (B), to appear."},{"key":"BF02579273_CR39","unstructured":"M. W. Padberg andM. R. Rao, Minimum cut-sets and b-matchings,to appear."},{"key":"BF02579273_CR40","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0012-365X(80)90057-6","volume":"32","author":"A. Schrijver","year":"1980","unstructured":"A. Schrijver, A counterexample to a conjecture of Edmonds and Giles,Discrete Math. 32 (1980) 213\u2013214.","journal-title":"Discrete Math."},{"key":"BF02579273_CR41","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0095-8956(77)90031-4","volume":"23","author":"P. D. Seymour","year":"1977","unstructured":"P. D. Seymour, The matroids with the max-flow min-cut property,J. Combinatorial Theory (B) 23 (1977) 189\u2013222.","journal-title":"J. Combinatorial Theory (B)"},{"key":"BF02579273_CR42","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0012-365X(78)90116-4","volume":"23","author":"P. D. Seymour","year":"1978","unstructured":"P. D. Seymour, A two-commodity cut theorem,Discrete Math. 23 (1978) 177\u2013181.","journal-title":"Discrete Math."},{"key":"BF02579273_CR43","first-page":"80","volume":"2","author":"N. Z. Shor","year":"1970","unstructured":"N. Z. Shor, Convergence rate of the gradient descent method with dilatation of the space,Kibernetika 2 (1970) 80\u201385 (English translation:Cybernetics 6 (1970) 102\u2013108).","journal-title":"Kibernetika"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579273.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579273\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579273","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T16:45:01Z","timestamp":1558197901000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,6]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1981,6]]}},"alternative-id":["BF02579273"],"URL":"https:\/\/doi.org\/10.1007\/bf02579273","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,6]]}}}