{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:40:56Z","timestamp":1771623656007,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1992,8,1]],"date-time":"1992-08-01T00:00:00Z","timestamp":712627200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1992,8]]},"DOI":"10.1007\/bf01580897","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:58:11Z","timestamp":1114678691000},"page":"121-160","source":"Crossref","is-referenced-by-count":46,"title":["Facets for the cut cone I"],"prefix":"10.1007","volume":"56","author":[{"given":"Michel","family":"Deza","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monique","family":"Laurent","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0195-6698(84)80022-0","volume":"5","author":"P. Assouad","year":"1984","unstructured":"P. Assouad, \u201cSur les in\u00e9galit\u00e9s valides dansL 1,\u201dEuropean Journal of Combinatorics 5 (1984) 99\u2013112.","journal-title":"European Journal of Combinatorics"},{"key":"CR2","first-page":"369","volume":"291","author":"P. Assouad","year":"1980","unstructured":"P. Assouad and C. Delorme, \u201cGraphes plongeables dansL 1,\u201dComptes Rendus de l'Acad\u00e9mie des Sciences de Paris 291 (1980) 369\u2013372.","journal-title":"Comptes Rendus de l'Acad\u00e9mie des Sciences de Paris"},{"key":"CR3","unstructured":"P. Assouad and M. Deza, \u201cMetric subspaces ofL 1,\u201dPublications Math\u00e9matiques d'Orsay, Vol. 3 (1982)."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/S0195-6698(89)80002-2","volume":"10","author":"D. Avis","year":"1989","unstructured":"D. Avis and Mutt, \u201cAll facets of the six point Hamming cone,\u201dEuropean Journal of Combinatorics 10 (1989) 309\u2013312.","journal-title":"European Journal of Combinatorics"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1002\/net.3230210602","volume":"21","author":"D. Avis","year":"1991","unstructured":"D. Avis and M. Deza, \u201cThe cut cone,L 1-embeddability, complexity and multicommodity flows,\u201dNetworks 21 (1991) 595\u2013617.","journal-title":"Networks"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0167-6377(83)90016-0","volume":"2","author":"F. Barahona","year":"1983","unstructured":"F. Barahona, \u201cThe max-cut problem on graphs not contractible toK 5,\u201dOperations Research Letters 2 (1983) 107\u2013111.","journal-title":"Operations Research Letters"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/0095-8956(86)90063-8","volume":"40","author":"F. Barahona","year":"1986","unstructured":"F. Barahona and M. Gr\u00f6tschel, \u201cOn the cycle polytope of a binary matroid,\u201dJournal of Combinatorial Theory B 40 (1986) 40\u201362.","journal-title":"Journal of Combinatorial Theory B"},{"issue":"3","key":"CR8","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F. Barahona","year":"1988","unstructured":"F. Barahona, M. Gr\u00f6tschel, M. J\u00fcnger and G. Reinelt, \u201cAn application of combinatorial optimization to statistical physics and circuit layout design,\u201dOperations Research 36(3) (1988) 493\u2013513.","journal-title":"Operations Research"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1287\/moor.10.2.340","volume":"10","author":"F. Barahona","year":"1985","unstructured":"F. Barahona, M. Gr\u00f6tschel and A.R. Mahjoub, \u201cFacets of the bipartite subgraph polytope,\u201dMathematics of Operations Research 10 (1985) 340\u2013358.","journal-title":"Mathematics of Operations Research"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01587084","volume":"44","author":"F. Barahona","year":"1989","unstructured":"F. Barahona, M. J\u00fcnger and G. Reinelt, \u201cExperiments in quadratic 0\u20131 programming,\u201dMathematical Programming 44 (1989) 127\u2013137.","journal-title":"Mathematical Programming"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F. Barahona","year":"1986","unstructured":"F. Barahona and A. R. Mahjoub, \u201cOn the cut polytope,\u201dMathematical Programming 36 (1986) 157\u2013173.","journal-title":"Mathematical Programming"},{"key":"CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-74341-2","volume-title":"Distance Regular Graphs","author":"A.E. Brower","year":"1989","unstructured":"A.E. Brower, A.M. Cohen and A. Neumaier,Distance Regular Graphs (Springer, Berlin, 1989)."},{"key":"CR13","volume-title":"\u201cTables of two-graphs,\u201d TH-Report 79-WSK-05","author":"F.C. Bussemaker","year":"1979","unstructured":"F.C. Bussemaker, R.A. Mathon and J.J. Seidel, \u201cTables of two-graphs,\u201d TH-Report 79-WSK-05, Technical University Eindhoven (Eindhoven, Netherlands, 1979)."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF01588778","volume":"49","author":"M. Conforti","year":"1990","unstructured":"M. Conforti, M.R. Rao and A. Sassano, \u201cThe equipartition polytope: parts I & II,\u201dMathematical Programming 49 (1990) 49\u201370, 71\u201391.","journal-title":"Mathematical Programming"},{"key":"CR15","unstructured":"C. De Simone, \u201cThe Hamming cone, the cut polytope and the boolean quadric polytope,\u201d preprint (1988)."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0012-365X(90)90056-N","volume":"79","author":"C. Simone De","year":"1989\/90","unstructured":"C. De Simone, \u201cThe cut polytope and the boolean quadric polytope,\u201dDiscrete Mathematics 79 (1989\/90) 71\u201375.","journal-title":"Discrete Mathematics"},{"key":"CR17","volume-title":"\u201cCollapsing and lifting for the cut cone,\u201d Report No. 265","author":"C. Simone De","year":"1989","unstructured":"C. De Simone, M. Deza and M. Laurent, \u201cCollapsing and lifting for the cut cone,\u201d Report No. 265, IASI-CNR (Roma, 1989)."},{"key":"CR18","first-page":"1037","volume":"134","author":"M. Deza","year":"1960","unstructured":"M. Deza, \u201cOn the Hamming geometry of unitary cubes,\u201dDoklady Akademii Nauk SSR 134 (1960) 1037\u20131040. [English translation in:Soviet Physics Doklady 5 (1961) 940\u2013943.]","journal-title":"Doklady Akademii Nauk SSR"},{"key":"CR19","unstructured":"M. Deza, \u201cLinear metric properties of binary codes,\u201dProceedings of the 4th Conference of USSR on Coding Theory and Transmission of Information, Moscow-Tachkent (1969) 77\u201385. [In Russian.]"},{"key":"CR20","first-page":"873","volume":"277","author":"M. Deza","year":"1973","unstructured":"M. Deza, \u201cMatrices de formes quadratiques non n\u00e9gatives pour des arguments binaires,\u201dComptes Rendus de l'Acad\u00e9mie des Sciences de Paris 277 (1973) 873\u2013875.","journal-title":"Comptes Rendus de l'Acad\u00e9mie des Sciences de Paris"},{"key":"CR21","first-page":"269","volume":"7","author":"M. Deza","year":"1982","unstructured":"M. Deza, \u201cSmall pentagonal spaces,\u201dRendiconti del Seminario Matematico di Brescia 7 (1982) 269\u2013282.","journal-title":"Rendiconti del Seminario Matematico di Brescia"},{"key":"CR22","volume-title":"\u201cThe inequicut cone,\u201d Research Report No. 89-04","author":"M. Deza","year":"1989","unstructured":"M. Deza, K. Fukuda and M. Laurent, \u201cThe inequicut cone,\u201d Research Report No. 89-04, GSSM, University of Tsukuba (Tokyo, 1989)."},{"key":"CR23","unstructured":"M. Deza, V.P. Grishukhin and M. Laurent, \u201cThe hypermetric cone is polyhedral,\u201d to appear in:Combinatorica."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF01580898","volume":"56","author":"M. Deza","year":"1992","unstructured":"M. Deza and M. Laurent, \u201cFacets for the cut cone II: Clique-web inequalities,\u201dMathematical Programming 56 (1992) 161\u2013188, this issue.","journal-title":"Mathematical Programming"},{"key":"CR25","unstructured":"J. Fonlupt, A.R. Mahjoub and J-P. Uhry, \u201cComposition of graphs and the bipartite subgraph polytope,\u201d to appear in:Discrete Mathematics."},{"key":"CR26","volume-title":"Computers and intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson,Computers and intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979)."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/S0195-6698(13)80064-9","volume":"11","author":"V.P. Grishukhin","year":"1990","unstructured":"V.P. Grishukhin, \u201cAll facets of the cut coneC n forn=7 are known,\u201dEuropean Journal of Combinatorics 11 (1990) 115\u2013117.","journal-title":"European Journal of Combinatorics"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0167-6377(81)90020-1","volume":"1","author":"M. Gr\u00f6tschel","year":"1981","unstructured":"M. Gr\u00f6tschel and W.R. Pulleyblank, \u201cWeakly bipartite graphs and the max-cut problem,\u201dOperations Research Letters 1 (1981) 23\u201327.","journal-title":"Operations Research Letters"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF01580870","volume":"47","author":"M. Gr\u00f6tschel","year":"1990","unstructured":"M. Gr\u00f6tschel and Y. Wakabayashi, \u201cFacets of the clique partitioning polytope,\u201dMathematical Programming 47 (1990) 367\u2013387.","journal-title":"Mathematical Programming"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F.O. Hadlock","year":"1975","unstructured":"F.O. Hadlock, \u201cFinding a maximum cut of planar graph in polynomial time,\u201dSIAM Journal on Computing 4 (1975) 221\u2013225.","journal-title":"SIAM Journal on Computing"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1287\/opre.13.3.388","volume":"13","author":"P.L. Hammer","year":"1965","unstructured":"P.L. Hammer, \u201cSome network flow problems solved with pseudo-boolean programming,\u201dOperations Research 13 (1965) 388\u2013399.","journal-title":"Operations Research"},{"key":"CR32","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BF01586090","volume":"32","author":"A.V. Karzanov","year":"1985","unstructured":"A.V. Karzanov, \u201cMetrics and undirected cuts,\u201dMathematical Programming 32 (1985) 183\u2013198.","journal-title":"Mathematical Programming"},{"key":"CR33","first-page":"17","volume-title":"Lecture notes in Mathematics No. 490","author":"J.B. Kelly","year":"1975","unstructured":"J.B. Kelly, \u201cHypermetric spaces,\u201dLecture notes in Mathematics No. 490 (Springer, Berlin, 1975) pp. 17\u201331."},{"key":"CR34","unstructured":"J.B. Kelly, unpublished."},{"key":"CR35","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M. Padberg","year":"1989","unstructured":"M. Padberg, \u201cThe Boolean quadric polytope: Some characteristics, facets and relatives,\u201dMathematical Programming 45 (1989) 139\u2013172.","journal-title":"Mathematical Programming"},{"key":"CR36","first-page":"373","volume":"112","author":"S. Poljak","year":"1987","unstructured":"S. Poljak and D. Turzik, \u201cOn a facet of the balanced subgraph polytope,\u201dCasopis Pro Pestovani Matematiky 112 (1987) 373\u2013380.","journal-title":"Casopis Pro Pestovani Matematiky"},{"key":"CR37","unstructured":"S. Poljak and D. Turzik, \u201cMax-cut in circulant graphs,\u201d to appear in:Annals of Discrete Mathematics."},{"issue":"3","key":"CR38","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/BF01788552","volume":"3","author":"P. Terwilliger","year":"1987","unstructured":"P. Terwilliger and M. Deza, \u201cClassification of finite connected hypermetric spaces,\u201dGraphs and Combinatorics 3(3) (1987) 293\u2013298.","journal-title":"Graphs and Combinatorics"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01580897.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01580897\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01580897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T15:12:12Z","timestamp":1556896332000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01580897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,8]]},"references-count":38,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1992,8]]}},"alternative-id":["BF01580897"],"URL":"https:\/\/doi.org\/10.1007\/bf01580897","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,8]]}}}