{"entities":{"Q1306454":{"pageid":1317204,"ns":120,"title":"Item:Q1306454","lastrevid":46843875,"modified":"2025-12-25T17:14:26Z","type":"item","id":"Q1306454","labels":{"en":{"language":"en","value":"Lifting theorems and facet characterization for a class of clique partitioning inequalities"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1347263"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$6A960843-5606-4329-80F7-A2BDF96057F6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"be074d81b892e6ca36eec81a0a285fd682063ae1","datavalue":{"value":{"text":"Lifting theorems and facet characterization for a class of clique partitioning inequalities","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1306454$1E0519D2-30F1-4F91-8621-51D4EFECADC0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f3254287ba43c925bf38d4f2c34c5dbb256cff9f","datavalue":{"value":"0941.90072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306454$278D07F2-E8BA-4796-BAA7-F96BEB87AF39","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4940c14772f4ffc69ca2987984732ce703187ba9","datavalue":{"value":"10.1016/S0167-6377(99)00029-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306454$630CC672-CC37-4958-AD19-9C7861FD74AB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0adbb1357f28935f1684fc542514f52f1a06d10f","datavalue":{"value":{"entity-type":"item","numeric-id":494222,"id":"Q494222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$E82FA749-2A58-4894-9AE0-1FC72EF85BB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c49051e68afdbc1acd5d988884e18df4ffecc4fa","datavalue":{"value":{"entity-type":"item","numeric-id":1270765,"id":"Q1270765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$8FDFBC80-BD9B-4D08-93C4-29F6042FBDBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"238b85ff82816e3018d1cabd35ed64f310f6add5","datavalue":{"value":{"entity-type":"item","numeric-id":1306453,"id":"Q1306453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$A5CE74E7-0FDA-4AE8-B74B-331A55B09BD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"058e02b14f73fa961e8230ed8e0d6de6f8c67a8b","datavalue":{"value":{"entity-type":"item","numeric-id":262242,"id":"Q262242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$A77348AC-64FE-40E0-8FFF-2A448970BA88","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$2FDA1141-EB3E-4EC0-8790-F7FF10ECEF3C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a9ff749b3707f7cb215f4483c5a296daee21d1bc","datavalue":{"value":{"time":"+1999-12-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1306454$19AA9C3B-D542-4F64-B6BF-9FF3557CAB3C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f0f81cc3dc93966eb345f4f70930df7f8cd8661e","datavalue":{"value":"In this paper we prove two lifting theorems for the clique partitioning polytope, which provide sufficient conditions for a valid inequality to be facet-defining. In particular, if a valid inequality defines a facet of the polytope corresponding to the compact graph \\(K_m\\) on \\(m\\) vertices, it defines a facet for the polytope corresponding to \\(K_n\\) for all \\(n>m\\). This answers a question raised by Gr\u00f6tschel and Wakabayashi. Further, for the case of arbitrary graphs, we characterize when the so-called 2-partition inequalities define facets.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306454$0052EC90-EB8B-4710-B540-79AABDB29B5E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306454$F0A8497B-FDD6-4EE4-8191-14720BCCC855","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2814976443bcccba0894e4fceb87b84d4d0a1d23","datavalue":{"value":"1347263","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306454$7DF946BE-81DE-42C0-A989-97BC9B90CB2C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d65bfc3ff47bed0c2aa04f46b5ec6cca5d37629","datavalue":{"value":"polyhedral combinatorics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306454$FA03E2E1-A3AE-4B6B-A053-A01A33B5F481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"747d0307b6dafcec6e50ba81d3396bbf3812302c","datavalue":{"value":"facets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306454$51A37C08-C99C-41A9-AF32-533F78EA066E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d1e0bc81013a06dddbed06be9e327564214a46e","datavalue":{"value":"lifting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306454$4F4C29BF-0CD6-439E-AE1E-310157EA5034","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c73176671a7372845a4821e48e43363604cbba95","datavalue":{"value":"clique partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306454$CD334809-04C8-4AFC-B02B-B3BA107D5869","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$1C990048-D4BD-4954-AA4A-FF7185909700","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"978d26cf9ebb109a01684eed1c2ad4d2d7a0d601","datavalue":{"value":{"entity-type":"item","numeric-id":2366610,"id":"Q2366610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$5A662D63-2958-452D-BB74-7C0D49DDF537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd9c914aa956f912ffcf34009354f07dcd2de28a","datavalue":{"value":{"entity-type":"item","numeric-id":4369763,"id":"Q4369763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$1F2637AF-F3AE-46A8-861E-B94253F5E792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"214019786e7fea7f2a603887965b4053a99361f2","datavalue":{"value":{"entity-type":"item","numeric-id":3753826,"id":"Q3753826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$1FDF487E-58CF-49BE-8037-BEF7FAB3CE26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6084bdc184628adc7fe57f950fb27bccae70ea2b","datavalue":{"value":{"entity-type":"item","numeric-id":752015,"id":"Q752015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$9020872A-826A-4532-9D00-7641AB453589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fd623ee12d7d804297522ca6768ffdf2608213a","datavalue":{"value":{"entity-type":"item","numeric-id":3972001,"id":"Q3972001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$7544598D-A895-4626-B1DC-3F9FAECA2945","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74d294277a463549f59bbc6fb06d14006e2c291b","datavalue":{"value":{"entity-type":"item","numeric-id":3859790,"id":"Q3859790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$8A850954-03DB-40D2-B6E0-EACA892F3B45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1e8c199d0a3738b5df7039fa423628b9c9f24f","datavalue":{"value":{"entity-type":"item","numeric-id":4040221,"id":"Q4040221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306454$95B8376E-36D9-49F8-8228-BC5CF72162EB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5757eb4a89c018fbeef8b4a114efa19c0d52ec66","datavalue":{"value":"https://doi.org/10.1016/s0167-6377(99)00029-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1306454$5C35F476-1231-4E60-8ACC-0728DD485AD9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d9919791dc7d1073c44e7c96eda43b5b540adec0","datavalue":{"value":"W1966088050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306454$44FF535B-5407-419C-BF70-461FD78E9670","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30b05a94e45071c1caad88b8753d434b88e771bc","datavalue":{"value":{"entity-type":"item","numeric-id":4537609,"id":"Q4537609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3af90bf34a6bf7017731faa0930cd48945b6fd63","datavalue":{"value":{"amount":"+0.8258435726165771","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306454$B3DD615D-02CB-4C22-8038-D94179E63DEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f63bcdf560f72fb74b4a16df2d380556e76a083e","datavalue":{"value":{"entity-type":"item","numeric-id":752015,"id":"Q752015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"776b348acbc0585a9eb2141ed54c86c938937867","datavalue":{"value":{"amount":"+0.8185513615608215","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306454$F87F5ABB-C4AF-4237-A2D4-219F6AA86AD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88c55fcc2a0088b28b4b4d3e3a9159f047d15d38","datavalue":{"value":{"entity-type":"item","numeric-id":1897366,"id":"Q1897366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1678476938a4c20ae93e366f2d83abd048ec4d77","datavalue":{"value":{"amount":"+0.8133203387260437","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306454$E0F78FDC-CAB7-40EB-9B21-83FA9AAE94E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecffcf3a1770653333e7c007b1722caa7121cd3e","datavalue":{"value":{"entity-type":"item","numeric-id":923115,"id":"Q923115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8667e165331c6068083b7ec9369eab236d30392d","datavalue":{"value":{"amount":"+0.8055405020713806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306454$4949C245-94D7-4D8F-88F9-61FF7F2D43A3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1306454","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1306454"}}}}}