{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T00:47:07Z","timestamp":1780361227662,"version":"3.54.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1984,2,1]],"date-time":"1984-02-01T00:00:00Z","timestamp":444441600000},"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":[[1984,2]]},"DOI":"10.1007\/bf02612354","type":"journal-article","created":{"date-parts":[[2007,4,27]],"date-time":"2007-04-27T06:54:07Z","timestamp":1177656847000},"page":"121-155","source":"Crossref","is-referenced-by-count":239,"title":["Roof duality, complementation and persistency in quadratic 0\u20131 optimization"],"prefix":"10.1007","volume":"28","author":[{"given":"P. L.","family":"Hammer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"P.","family":"Hansen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B.","family":"Simeone","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF02612354_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"B. Aspvall, M.F. Plass and R.E. Tarjan, \u201cA linear-time algorithm for testing the truth of certain quantified Boolean formulas\u201d,Information Processing Letters 8 (1979) 121\u2013123.","journal-title":"Information Processing Letters"},{"key":"BF02612354_CR2","first-page":"179","volume-title":"Mathematics of the decision sciences, Part I","author":"M.L. Balinski","year":"1968","unstructured":"M.L. Balinski, \u201cInteger programming: Methods, uses, computation\u201d, in: G.B. Dantzig and A.F. Veinott, Jr., eds.,Mathematics of the decision sciences, Part I (American Mathematical Society, Providence, 1968), pp 179\u2013256."},{"key":"BF02612354_CR3","first-page":"38","volume-title":"Mathematics of the decision sciences, Part I","author":"M.L. Balinski","year":"1968","unstructured":"M.L. Balinski, \u201cNotes on a constructive approach to linear programming\u201d, in: G.B. Dantzig and A.F. Veinott, Jr., eds.,Mathematics of the decision sciences, Part I (American Mathematical Society, Providence, 1968) pp. 38\u201364."},{"key":"BF02612354_CR4","doi-asserted-by":"crossref","unstructured":"S. Cook, \u201cThe complexity of theorem proving procedures\u201d,Proceedings of the Third Symposium of the Association of Computing Machinery on the Theory of Computing (1971) 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"BF02612354_CR5","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"M.L. Fischer","year":"1978","unstructured":"M.L. Fischer, G.L. Nemhauser and L.A. Wolsey, \u201cAn analysis of approximations for maximizing submodular set functions\u2014I\u201d,Mathematical Programming 14 (1978) 265\u2013294.","journal-title":"Mathematical Programming"},{"key":"BF02612354_CR6","doi-asserted-by":"crossref","first-page":"166","DOI":"10.4153\/CJM-1965-016-2","volume":"17","author":"D.R. Fulkerson","year":"1965","unstructured":"D.R. Fulkerson, A.J. Hoffman and M.H. McAndrew, \u201cSome properties of graphs with multiple edges\u201d,Canadian Journal of Mathematics 17 (1965), 166\u2013177.","journal-title":"Canadian Journal of Mathematics"},{"key":"BF02612354_CR7","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/BFb0120892","volume":"12","author":"G. Gallo","year":"1980","unstructured":"G. Gallo, P.L. Hammer and B. Simeone, \u201cQuadratic knapsack problems\u201dMathematical Programming Studies 12 (1980) 132\u2013149.","journal-title":"Mathematical Programming Studies"},{"key":"BF02612354_CR8","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0167-5060(08)70818-5","volume":"4","author":"P.L. Hammer","year":"1979","unstructured":"P.L. Hammer, \u201cBoolean elements in combinatorial optimization\u201d,Annals of Discrete Mathematics 4 (1979) 51\u201371.","journal-title":"Annals of Discrete Mathematics"},{"key":"BF02612354_CR9","first-page":"421","volume":"26","author":"P.L. Hammer","year":"1981","unstructured":"P.L. Hammer and P. Hansen, \u201cLogical relations in quadratic 0\u20131 programming\u201d,Revue Roumaine de Math\u00e9matiques Pures et Appliqu\u00e9es 26 (1981) 421\u2013429.","journal-title":"Revue Roumaine de Math\u00e9matiques Pures et Appliqu\u00e9es"},{"key":"BF02612354_CR10","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1137\/0603052","volume":"3","author":"P.L. Hammer","year":"1982","unstructured":"P.L. Hammer, P. Hansen and B. Simeone, \u201cVertices belonging to all or to no maximum stables sets of a graph\u201d,SIAM Journal on Algebraic and Discrete Methods 3 (1982) 511\u2013522.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"BF02612354_CR11","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/B978-0-12-468662-5.50019-7","volume-title":"Nonlinear Programming 4","author":"P.L. Hammer","year":"1981","unstructured":"P.L. Hammer, P. Hansen and B. Simeone, \u201cUpper planes of quadratic 0\u20131 functions and stability in graphs\u201d,Nonlinear Programming 4 (Academic Press, New York, 1981), pp. 395\u2013414."},{"key":"BF02612354_CR12","first-page":"159","volume":"19","author":"P.L. Hammer","year":"1977","unstructured":"P.L. Hammer, U.N. Peled and S. Sorensen \u201cPseudo-boolean functions and game theory, I, Core elements and Shapley value\u201d,Cahiers du Centre d'Etudes de Recherche Op\u00e9rationnelle 19 (1977) 159\u2013176.","journal-title":"Cahiers du Centre d'Etudes de Recherche Op\u00e9rationnelle"},{"key":"BF02612354_CR13","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-0348-5321-7_5","volume-title":"Numerische Methoden bei Optimierung Vol. II","author":"P.L. Hammer","year":"1974","unstructured":"P.L. Hammer and I.G. Rosenberg, \u201cLinear decomposition of a positive group-boolean function\u201d, in: L. Collatz and W. Wetterling, eds.Numerische Methoden bei Optimierung Vol. II (Birkh\u00e4user, Basel and Stuttgart, 1974) pp. 51\u201362."},{"key":"BF02612354_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-85823-9","volume-title":"Boolean methods in operations research and related areas","author":"P.L. Hammer","year":"1968","unstructured":"P.L. Hammer and S. Rudeanu,Boolean methods in operations research and related areas (Springer, Berlin, New York, 1968)."},{"key":"BF02612354_CR15","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/978-94-011-7557-9_21","volume-title":"Combinatorial programming, methods and applications","author":"P. Hansen","year":"1975","unstructured":"P. Hansen, \u201cFonctions d'\u00e9valuation et p\u00e9nalites pour les programmes quadratiques en variables 0\u20131\u201d, in: B. Roy, ed.Combinatorial programming, methods and applications, (Reidel, Dordrecht, 1975) pp. 361\u2013370."},{"key":"BF02612354_CR16","series-title":"Colloque International du Centre National de la Recherche Scientifique","first-page":"215","volume-title":"Probl\u00e8mes combinatoires et th\u00e9orie des graphes","author":"P. Hansen","year":"1978","unstructured":"P. Hansen, \u201cLabelling algorithms for balance in signed graphs\u201d, in: J.-C. Bermond et al., eds.,Probl\u00e8mes combinatoires et th\u00e9orie des graphes, Colloque International du Centre National de la Recherche Scientifique, No. 260 (Editions Centre National de la Recherche Scientifique, Paris, 1978) pp. 215\u2013217."},{"key":"BF02612354_CR17","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0167-5060(08)70343-1","volume":"5","author":"P. Hansen","year":"1979","unstructured":"P. Hansen, \u201cMethods of nonlinear 0\u20131 programming\u201d,Annals of Discrete Mathematics 5 (1979) 53\u201369.","journal-title":"Annals of Discrete Mathematics"},{"key":"BF02612354_CR18","series-title":"CORR 79-39","volume-title":"A class of quadratic pseudoboolean functions whose maximization is reducible to a network flow problem","author":"P. Hansen","year":"1979","unstructured":"P. Hansen and B. Simeone, \u201cA class of quadratic pseudoboolean functions whose maximization is reducible to a network flow problem,\u201d CORR 79-39, Department of Combinatorics and Optimization, University of Waterloo, (Waterloo, Ontario, 1979)."},{"key":"BF02612354_CR19","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":"BF02612354_CR20","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0167-5060(08)70830-6","volume":"4","author":"E.L. Lawler","year":"1979","unstructured":"E.L. Lawler, \u201cShortest path and network flow algorithms\u201d,Annals of Discrete Mathematics 4 (1979) 251\u2013263.","journal-title":"Annals of Discrete Mathematics"},{"key":"BF02612354_CR21","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"G.L. Nemhauser and L.E. Trotter, \u201cVertex packings: Structural properties and algorithms\u201d,Mathematical Programming 8 (1975) 232\u2013248.","journal-title":"Mathematical Programming"},{"key":"BF02612354_CR22","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01593772","volume":"12","author":"J.C. Picard","year":"1977","unstructured":"J.C. Picard and M. Queyranne, \u201cOn the integer valued variables in the linear vertex packing problem\u201d,Mathematical Programming 12 (1977) 97\u2013101.","journal-title":"Mathematical Programming"},{"key":"BF02612354_CR23","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1287\/mnsc.17.3.200","volume":"17","author":"J. Rhys","year":"1970","unstructured":"J. Rhys, \u201cA selection problem of shared fixed costs and networks\u201d,Management Science 17 (1970) 200\u2013207.","journal-title":"Management Science"},{"key":"BF02612354_CR24","first-page":"71","volume":"17","author":"I.G. Rosenberg","year":"1975","unstructured":"I.G. Rosenberg, \u201cReduction of bivalent maximization to the quadratic case\u201d,Cahiers du Centre d'Etudes de Recherche Op\u00e9rationnelle 17 (1975) 71\u201379.","journal-title":"Cahiers du Centre d'Etudes de Recherche Op\u00e9rationnelle"},{"key":"BF02612354_CR25","volume-title":"Quadratic 0\u20131 programming, boolean functions and graphs","author":"B. Simeone","year":"1979","unstructured":"B. Simeone, \u201cQuadratic 0\u20131 programming, boolean functions and graphs\u201d, Doctoral Dissertation, University of Waterloo (Waterloo, Ontario, 1979)."},{"key":"BF02612354_CR26","unstructured":"B. Simeone, \u201cA generalizaed consensus approach to non-linear 0\u20131 optimization\u201d,Journal of the Association of Computing Machinery, forthcoming."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02612354.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02612354\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02612354","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T08:34:25Z","timestamp":1558341265000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02612354"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,2]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1984,2]]}},"alternative-id":["BF02612354"],"URL":"https:\/\/doi.org\/10.1007\/bf02612354","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1984,2]]}}}