{"entities":{"Q752015":{"pageid":753864,"ns":120,"title":"Item:Q752015","lastrevid":49445548,"modified":"2026-01-07T04:19:32Z","type":"item","id":"Q752015","labels":{"en":{"language":"en","value":"Facets of the clique partitioning polytope"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4179155"}},"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":"Q752015$6D6E1415-4047-4DC2-B75D-2DD14462F567","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3f744bd29ead86f9bccb25ce9d8b23018168d122","datavalue":{"value":{"text":"Facets of the clique partitioning polytope","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q752015$B1C84C15-A470-4D1A-925B-1BCA07B7898F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0597efd5255dd86bea55487343aa81e495230fb9","datavalue":{"value":"0715.90092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752015$5874C5E8-7BE2-4043-A836-3636FFBB8985","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"38994efa9571a59a60717b28bc28233ea83c2afc","datavalue":{"value":"10.1007/BF01580870","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752015$2C6E7AB9-E0BF-400A-BF55-DBFF01E6B9FE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c79d63a974620aa9dd22e3cdec2e56a2714b61d9","datavalue":{"value":{"entity-type":"item","numeric-id":202055,"id":"Q202055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$0755A995-17AD-4C04-9EF6-A35DAE672682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00dcd34d2a42ffd4c9646545f08dca80da5e12dd","datavalue":{"value":{"entity-type":"item","numeric-id":590171,"id":"Q590171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$34AF6C2E-288C-4F2C-AE81-CFEDB2177CDA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$AF404A67-FCA0-4A1E-ADF6-1B0E0FB0E5B3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q752015$BE52A415-0DDE-4C96-8922-E170D0D58B9D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f7f714a14f5f901dcb6235e6bff8b8447243f290","datavalue":{"value":"The clique partitioning problem in an edge weighted graph (with negative weights in general) is that of finding a partition of its vertices into blocks such that the sum of the weights on all edges that are within blocks is minimized. This problem is NP complete. In this paper various facets of the polytope of clique partitions are described. This endeavor is potentially useful for actually solving examples of such problems if these facets turn out to be the ones relevant at the solution point.    Facets are obtained corresponding to 2-partitions, 2-chorded cycles, paths and wheels. Triangle inequality constraints and 2-partition inequalities are said to be often enough for utility in examples.","type":"string"},"datatype":"string"},"type":"statement","id":"Q752015$9B340D8B-E24A-48FE-A14C-A84AF1093A09","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752015$1D8AD8CE-2271-41C7-8DB7-524C8FBCAD98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752015$ED88BF7F-0AE0-42AC-83AE-FE1828434346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752015$E4264B4F-4F45-41F0-A78C-D96EB24DE7FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752015$C91AE3E3-2C2D-42B9-AEB5-57455B91AA32","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"13b15d559c18fc4bd85baf6b49c972ffe6f933d8","datavalue":{"value":"4179155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752015$7CAA6247-8C55-405B-B4D0-989651A48800","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c73176671a7372845a4821e48e43363604cbba95","datavalue":{"value":"clique partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q752015$E3C01AC2-2659-4CBB-998B-817B5B0BC27F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"edc72ed947b68f1600dc8ccb3bed861ae50c04b9","datavalue":{"value":"edge weighted graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q752015$7232BB63-7816-4DF4-A922-070A4428D4B1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b61c0d549074efcb0311df2e10210a92935b8fd8","datavalue":{"value":{"entity-type":"item","numeric-id":228778,"id":"Q228778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$0FD61582-B84F-4603-97F0-036B8566F0E9","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":"Q752015$56C22CAF-732A-4B5C-9395-25FB5B4E16B3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"93512bfdc47afc24e7dc7bba727163eb15783f98","datavalue":{"value":{"entity-type":"item","numeric-id":1164937,"id":"Q1164937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$0FD6486B-22B4-44D1-82FF-018500962401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$E98137BD-6D65-4262-94F4-A0B74A06DF61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8f80a19eef3ef00c63528b7a5312dd804775280","datavalue":{"value":{"entity-type":"item","numeric-id":1122492,"id":"Q1122492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$BAFC7D85-8CD3-4802-92ED-CACC29410A4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da2a85c3cfc10c27f1e9d72af98eae1314212dae","datavalue":{"value":{"entity-type":"item","numeric-id":4742231,"id":"Q4742231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$500D75CD-9E6B-42AF-92D2-4C97C67DB6D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1118bb4fb184b6004831919f29d88635fb92da7","datavalue":{"value":{"entity-type":"item","numeric-id":3907360,"id":"Q3907360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$81CE2DBE-6147-45B1-B344-70E23A1A834B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b7ba566095a1742cf651610ce6562fc41247c5a","datavalue":{"value":{"entity-type":"item","numeric-id":4742505,"id":"Q4742505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$57623DCF-9AAD-4695-9BBD-FA554D79E061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60774c2a55e2d986ec7479f6d1e87915326ecfd8","datavalue":{"value":{"entity-type":"item","numeric-id":761244,"id":"Q761244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$2B589F13-B68E-48B9-ABCE-5ABFD6FE3F73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$7FBA8B97-A692-4FAA-9DC9-7219C6A8C807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c341b3be59bb3ca0f3d4614aa9ada6b1dc4bdd27","datavalue":{"value":{"entity-type":"item","numeric-id":3038367,"id":"Q3038367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$55BCFE6F-92AB-450D-B64F-3CFAFD9903F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12ef07c96efcb62b3d0eb51b255877bd24b42dda","datavalue":{"value":{"entity-type":"item","numeric-id":3745273,"id":"Q3745273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752015$9C253426-C80C-4CCE-86AD-BBF8CC3BF9CB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8b035c69c7f6d4c4993e183cd00da7f0e5e8eb24","datavalue":{"value":"https://doi.org/10.1007/bf01580870","type":"string"},"datatype":"url"},"type":"statement","id":"Q752015$BD3618DC-D18D-41A3-8ACE-EC468B69622C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ce5fdbfd5e3ea1011d6b3189251ec61384d90c66","datavalue":{"value":"W2047893320","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752015$7A516984-C0FF-4276-A329-DE81508326AE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cd3aeb46e7b0c2522669aac7a0c981126c56deb","datavalue":{"value":{"entity-type":"item","numeric-id":3972001,"id":"Q3972001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"261b9bfce1fae81b34f2ac9794b6a99943546f07","datavalue":{"value":{"amount":"+0.9052602648735046","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":"Q752015$44270DD9-05FA-4565-ADF5-055031F5720A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce2059b29cd653c466ae9a9ace322fba289b7f72","datavalue":{"value":{"entity-type":"item","numeric-id":1306454,"id":"Q1306454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35341660c357efc8fcd071c19212c8410c7f91f3","datavalue":{"value":{"amount":"+0.9036278128623962","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":"Q752015$198D252D-00B6-4935-B971-6E51430DC4D7","rank":"normal"},{"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":"fd576f76f8ffa61bb48f20df67a06fd4d9c03328","datavalue":{"value":{"amount":"+0.9017404913902284","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":"Q752015$827390DB-1111-4498-9390-6D80988FF6F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33896f0a765723fb3fe2b894cc5aee76d7f3a73b","datavalue":{"value":{"entity-type":"item","numeric-id":1420411,"id":"Q1420411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"627abad8f3a760362a21fbcb60703988ac602ee0","datavalue":{"value":{"amount":"+0.9016061425209044","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":"Q752015$397954D0-4330-4613-82FA-A822DEFD4F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a655a699c11e13f2eafcf9fce43157f3d2a437e6","datavalue":{"value":{"entity-type":"item","numeric-id":2366610,"id":"Q2366610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"963aa4da6a16e6c5c65f6224756fdd5a8402fe7f","datavalue":{"value":{"amount":"+0.8268513083457947","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":"Q752015$F10C8B7F-E8F0-45EE-82B1-1F4CCA03FE55","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:752015","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:752015"}}}}}