{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:10:37Z","timestamp":1768108237467,"version":"3.49.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2005,11,10]],"date-time":"2005-11-10T00:00:00Z","timestamp":1131580800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2005,11,10]],"date-time":"2005-11-10T00:00:00Z","timestamp":1131580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2006,7]]},"DOI":"10.1007\/s10107-004-0504-0","type":"journal-article","created":{"date-parts":[[2005,11,10]],"date-time":"2005-11-10T19:57:22Z","timestamp":1131652642000},"page":"367-390","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["A polyhedral study of the generalized vertex packing problem"],"prefix":"10.1007","volume":"107","author":[{"given":"Hanif D.","family":"Sherali","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Cole Smith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,11,10]]},"reference":[{"key":"504_CR1","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1287\/moor.23.2.359","volume":"23","author":"Adams","year":"2","unstructured":"Adams, W.P., Lassiter, J.B., Sherali, H.D.: Persistency in 0-1 polynomial programming. Math. Oper. Res. 23 (2), 359\u2013389 (1998)","journal-title":"Math. Oper. Res."},{"key":"504_CR2","unstructured":"Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows. John Wiley & Sons, second edition, New York, NY, 1990"},{"key":"504_CR3","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/0095-8956(75)90041-6","volume":"18","author":"Chv\u00e1tal","year":"1982","unstructured":"Chv\u00e1tal, V.: On certain polytopes associated with graphs. J. Comb. Theory, Series B 18, 138\u2013154 (1982)","journal-title":"J. Comb. Theory, Series B"},{"key":"504_CR4","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, NY, 1979"},{"key":"504_CR5","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/0095-8956(86)90087-0","volume":"40","author":"Gr\u00f6tschel","year":"1986","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Relaxations of vertex packing. J. Comb. Theory, Series B 40, 330\u2013343 (1986)","journal-title":"J. Comb. Theory, Series B"},{"key":"504_CR6","doi-asserted-by":"publisher","first-page":"48","DOI":"10.2307\/2033241","volume":"7","author":"Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning tree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"504_CR7","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/BF01580222","volume":"6","author":"Nemhauser","year":"1974","unstructured":"Nemhauser, G.L., Trotter, L.E.: Properties of vertex packing and independence system polyhedra. Math. Program. 6, 48\u201361 (1974)","journal-title":"Math. Program."},{"key":"504_CR8","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: structural properties and algorithms. Math. Program. 8, 232\u2013248 (1975)","journal-title":"Math. Program."},{"key":"504_CR9","doi-asserted-by":"crossref","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. John Wiley & Sons, New York, NY, 1988","DOI":"10.1002\/9781118627372"},{"key":"504_CR10","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0305-0548(92)90067-F","volume":"19","author":"Pardalos","year":"1992","unstructured":"Pardalos, P.M., Rodgers, G.P.: A branch and bound algorithm for the maximum clique problem. Comput. Oper. Res. 19, 363\u2013375 (1992)","journal-title":"Comput. Oper. Res."},{"key":"504_CR11","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01593772","volume":"12","author":"Picard","year":"1977","unstructured":"Picard, J.-C., Queyranne, M.: On the integer-valued variables in the linear vertex packing problem. Math. Program. 12, 97\u2013101 (1977)","journal-title":"Math. Program."},{"key":"504_CR12","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Disc. Math. 3, 411\u2013430 (1990)","journal-title":"SIAM J. Disc. Math."},{"key":"504_CR13","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0166-218X(92)00190-W","volume":"52","author":"Sherali","year":"1994","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Disc. Appl. Math. 52, 83\u2013106 (1994)","journal-title":"Disc. Appl. Math."},{"key":"504_CR14","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1287\/opre.46.3.396","volume":"46","author":"Sherali","year":"1998","unstructured":"Sherali, H.D., Adams, W.P., Driscoll, P.: Exploiting special structures in constructing a hierarchy of relaxations for 0-1 mixed integer problems. Oper. Res. 46, 396\u2013405 (1998)","journal-title":"Oper. Res."},{"key":"504_CR15","unstructured":"Sherali, H.D., Smith, J.C., Trani, A.A.: An airspace planning model for selecting flight-plans under workload, safety, and equity considerations. To appear in Transportation Science, 2000"},{"key":"504_CR16","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1287\/trsc.34.4.321.12326","volume":"34","author":"Sherali","year":"2000","unstructured":"Sherali, H.D., Smith, J.C., Trani, A.A., Sale, S.: National airspace sector occupancy and conflict analysis models for evaluating scenarios under the free-flight paradigm. Trans. Sci. 34, 321\u2013336 (2000)","journal-title":"Trans. Sci."},{"key":"504_CR17","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/0012-365X(75)90077-1","volume":"12","author":"Trotter","year":"1975","unstructured":"Trotter, L.E., Jr: A class of facet producing graphs for vertex packing polyhedra. Disc. Math. 12, 373\u2013388 (1975)","journal-title":"Disc. Math."},{"key":"504_CR18","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/BF01580383","volume":"11","author":"Wolsey","year":"1976","unstructured":"Wolsey, L.A.: Further facet generating procedures for vertex packing polytopes. Math. Program. 11, 158\u2013163 (1976)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-004-0504-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-004-0504-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-004-0504-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-004-0504-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,14]],"date-time":"2022-05-14T01:09:06Z","timestamp":1652490546000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-004-0504-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11,10]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["504"],"URL":"https:\/\/doi.org\/10.1007\/s10107-004-0504-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,11,10]]},"assertion":[{"value":"27 February 2002","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2003","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 November 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}