{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:57Z","timestamp":1759063557139},"reference-count":12,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":10632,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1977,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Facets of the set packing polytope provide strong cutting planes for set packing and partitioning problems. Set packing polytopes are in a one\u2010to\u2010one correspondence with graphs. The facets of P(G), the set packing polytope associated with the graph G, are related to certain subgraphs of G. Of particular interest are those subgraphs G\u2032 which are facet producing, i.e., which give rise to facets of P(G\u2032) that cannot be obtained by lifting a facet of P(G\u2032 \u2010 {x}), for any vertex x of G\u2032. In this paper we characterize the facets of the set packing polytopes associated with the class of graphs obtained by Chv\u00e1tal's substitution procedure, and give necessary and sufficient conditions for these graphs to be facet\u2010producing.<\/jats:p>","DOI":"10.1002\/net.3230070307","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T03:47:59Z","timestamp":1178855279000},"page":"267-284","source":"Crossref","is-referenced-by-count":6,"title":["Graph substitution and set packing polytopes"],"prefix":"10.1002","volume":"7","author":[{"given":"E.","family":"Balas","sequence":"first","affiliation":[]},{"given":"E.","family":"Zemel","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1018115"},{"key":"e_1_2_1_3_2","volume-title":"MSRR No. 374","author":"Balas E.","year":"1975"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal V. \u201cOn Certain Polytopes Associated with Graphs \u201dJ. of Combinatorial Theory B 18 1975 pp.138\u2013154.","DOI":"10.1016\/0095-8956(75)90041-6"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1962-10791-5"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584085"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580222"},{"key":"e_1_2_1_9_2","unstructured":"Padberg M. W. \u201cEssays in Integer Programming \u201dPh.D. Thesis Carnegie\u2010Mellon University May1971."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580121"},{"key":"e_1_2_1_11_2","volume-title":"GBA Working Paper No. 75\u2013105","author":"Padberg M. W.","year":"1975"},{"key":"e_1_2_1_12_2","unstructured":"Trotter L. E. \u201cA Class of Facet Producing Graphs for Vertex Packing Polyhedra \u201dTechnical Report No. 78 Yale University February1974."},{"key":"e_1_2_1_13_2","volume-title":"MSRR No. 354","author":"Zemel E.","year":"1974"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230070307","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230070307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T09:49:01Z","timestamp":1699782541000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230070307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977,9]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1977,9]]}},"alternative-id":["10.1002\/net.3230070307"],"URL":"https:\/\/doi.org\/10.1002\/net.3230070307","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1977,9]]}}}