{"entities":{"Q1070249":{"pageid":1081001,"ns":120,"title":"Item:Q1070249","lastrevid":69563904,"modified":"2026-04-13T07:52:06Z","type":"item","id":"Q1070249","labels":{"en":{"language":"en","value":"\\(K_ i\\)-covers. I: Complexity and polytopes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3935091"}},"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":"Q1070249$3DD3A48D-1B83-4D76-A6FC-C8EA524409EE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ec099129cbcdb11fec944f7dbf90d5045af9f2e5","datavalue":{"value":{"text":"\\(K_ i\\)-covers. I: Complexity and polytopes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1070249$5C1F8C85-76D8-4B22-94A3-89FAD52FA950","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8beecbe4ac5a66a24e5fd07dded6b6f2b30ebea1","datavalue":{"value":"0584.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070249$99F6D5F1-5B75-4C9B-8729-8226064C7760","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4fc576b6ceb35f19fa19cfb1dac86610b81d6a5d","datavalue":{"value":"10.1016/0012-365X(86)90156-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070249$EB78420E-8C36-48F7-879F-CF063400A81C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa9a170b566faa650496c61eaa134019d05c6a23","datavalue":{"value":{"entity-type":"item","numeric-id":203960,"id":"Q203960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$8A6FC399-73CC-44E7-95DE-4667F9091E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eac3bc3b952de30e0dbd044a5b978d4bbca81a36","datavalue":{"value":{"entity-type":"item","numeric-id":1070246,"id":"Q1070246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$371B0C25-BCF4-465C-B466-272DA64F1054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d752a8c8ec156de44a5b16b085911c20996c2330","datavalue":{"value":{"entity-type":"item","numeric-id":1070247,"id":"Q1070247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$11C84555-FCD1-4A26-9DBD-B958ABF3C123","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$81BAC79F-509D-431D-85F7-C171C4E0D097","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1070249$C0158A76-40D1-49DB-9860-46D9DD1ABA12","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"66c5c35104433f7bbb301d2d6eca6afee7d0fa7c","datavalue":{"value":"In a graph \\(G\\) a \\(K_ i\\) is a complete subgraph of size i. A \\(K_ i\\)-cover of \\(G\\) is a set \\(C\\) of \\(K_{i-1}'s\\) of \\(G\\) such that every \\(K_ i\\) in \\(G\\) contains at least one \\(K_{i-1}\\) from \\(C\\). It is proved that the problem of determining whether a general graph has a \\(K_ i\\)-cover (i\\(\\geq 2)\\) of cardinality \\(\\leq k\\) is NP-complete. For chordal graphs with fixed maximum clique size, the problem is shown to be polynomial. A partial characterization for the \\((K_{i-1}-K_ i)\\)-incidence polytope is given by some classes of facets for which the separation problem can be solved in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070249$C6E89371-27C1-4DF3-8054-9A7AA962BA46","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070249$0B0F5A42-9B3A-4242-A132-C85CC7F6D2B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ddd8cb1932c6bc41681458db5f685a2a286fde55","datavalue":{"value":"52Bxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070249$F5437437-1D79-46F6-8447-3D50745C3E25","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d30aa02f7d3dec381096c20b3e05c65991029a9","datavalue":{"value":"3935091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070249$FE7AD0A5-AE49-4657-86E8-D41D155CAE3B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7e1cd75562600af0ef91e6c84cc6237f3c20f94","datavalue":{"value":"complete subgraph cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070249$25D3559D-B97C-41D2-876B-15D3A103105F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc71c5c020e27277fe21513712681fac742b15ed","datavalue":{"value":"incidence polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q1070249$094699CC-9AD2-4ABA-AC3C-7B374D6F9F5C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"310474df49d5cc257d2ca64a8f6a6e037877244b","datavalue":{"value":{"entity-type":"item","numeric-id":789007,"id":"Q789007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$11396B86-E98C-45F5-BE06-E26DE59049B7","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":"Q1070249$FEBB225B-6B30-46FF-B4B2-8B36F3E83841","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c67729b1304819cd23b80be0e5e92a17db360b2d","datavalue":{"value":{"entity-type":"item","numeric-id":4117604,"id":"Q4117604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$D1E5FFFF-08C3-4A80-8210-559D5A5874C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"273bb8be43b497baa3a710fb525da21d668a4d19","datavalue":{"value":{"entity-type":"item","numeric-id":3699730,"id":"Q3699730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$4BFAD827-96B4-4B56-A285-20DF04BED95A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"871b0b619dcdcfea503ebb95e9e10caab2448bd3","datavalue":{"value":{"entity-type":"item","numeric-id":4726054,"id":"Q4726054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$ED1FA6C4-827B-4741-AD57-A4063A6BE835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9b4b0263bf157bc56ee9f4278362c292a571a65","datavalue":{"value":{"entity-type":"item","numeric-id":1147168,"id":"Q1147168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$18BAEBBD-5A8F-45D4-BD36-40D5B900BF1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3ecc4ed854f4c2fb93ed2e8327283eb9cc15cf0","datavalue":{"value":{"entity-type":"item","numeric-id":1393418,"id":"Q1393418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$79AE46C6-A652-44F6-8633-943DCFE087BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e23b074681d23fbbf37ab8b3658aab89c8a88aaa","datavalue":{"value":{"entity-type":"item","numeric-id":1050357,"id":"Q1050357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$7FAC981B-21BF-43DC-B6AE-AE78D1D350E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33959e8c3fbe7080f98305389592daf8f06321e","datavalue":{"value":{"entity-type":"item","numeric-id":5634016,"id":"Q5634016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$5254B47E-F134-4DE9-A38E-40CDF714E877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"620e7dd38bca19d2cb03eef38480510c6c765fe8","datavalue":{"value":{"entity-type":"item","numeric-id":3699731,"id":"Q3699731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$9C66774C-5589-4795-B86A-23E2A78EC595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$004F9FE8-135A-4539-91F4-4750368E1CE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1744afac4c45f065c4a9c50861775137377ee1b0","datavalue":{"value":{"entity-type":"item","numeric-id":3849459,"id":"Q3849459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$8029B05A-9A79-4658-B245-392913F2A128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b93f8e116857da1c2d9e0d6cc4d460b9a69e44f","datavalue":{"value":{"entity-type":"item","numeric-id":3328286,"id":"Q3328286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$7E515D71-B9C3-46B6-9FB2-7933DD25B4D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e067f99cb7a4495195e48c0195aaefd807ea07e5","datavalue":{"value":{"entity-type":"item","numeric-id":3048580,"id":"Q3048580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$DE837767-9DB8-4481-B542-CFDEEDD6C6DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e34bc8de7dff9e6ae38acf775674b87311a55dc0","datavalue":{"value":{"entity-type":"item","numeric-id":1169411,"id":"Q1169411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$0E1822A7-A921-45E5-868B-3C92879E7259","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$3FA2B83C-85C8-4033-8F9D-FA41F9954D8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e138268b388c59cc350422a307264a1cbe02595","datavalue":{"value":{"entity-type":"item","numeric-id":5181532,"id":"Q5181532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$DB7C8F14-ED7B-4573-A6EF-38751813B937","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8592b19f12bd09556a4de81ad49778d747c4f77b","datavalue":{"value":{"entity-type":"item","numeric-id":4124209,"id":"Q4124209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$BFD0121D-14EC-4F6B-A9C6-7C0C4373587D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6542352e47dd34fbda695c41fd84595fda3ecebd","datavalue":{"value":{"entity-type":"item","numeric-id":1220520,"id":"Q1220520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$364C90E2-F9BB-4738-803E-556CA006D8EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c95488d33c7f5f660efc9a0540767728ccb24d3","datavalue":{"value":{"entity-type":"item","numeric-id":3921260,"id":"Q3921260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1070249$606218D4-3652-491B-AE11-B43189A247BB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ecd21d823358f98aa0a64450d3ec20d258126a4f","datavalue":{"value":"https://doi.org/10.1016/0012-365x(86)90156-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1070249$178AEF02-94EC-4E09-A5C8-346918C2AECB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"05a3346a21b90947710f89beb2754a7efeea47f8","datavalue":{"value":"W1966227787","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1070249$210EA42A-A272-4282-B569-146F1128EB26","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8217722403b982830b573c94112f346711eb55cd","datavalue":{"value":{"entity-type":"item","numeric-id":1262127,"id":"Q1262127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c39fd98fdbb3c1b00bcbdb6d5a9fdc124d6803e","datavalue":{"value":{"amount":"+0.851315975189209","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":"Q1070249$0C581EFF-7CBC-45CF-9DA1-F521B031146C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"405c1b8fd65701160e1b25c9eda65dc5c7be7ceb","datavalue":{"value":{"entity-type":"item","numeric-id":3472137,"id":"Q3472137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9641dca5426c23690642c3d65061fa473e96cc4","datavalue":{"value":{"amount":"+0.8410841822624207","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":"Q1070249$4113BCE8-0DE5-4D86-BDB1-C071A599F71D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c14a930fb44e14bd6b2210ce4015c4e038d43ab8","datavalue":{"value":{"entity-type":"item","numeric-id":4016827,"id":"Q4016827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be75c206cf1193170ff43101704917041016a25f","datavalue":{"value":{"amount":"+0.8074759244918823","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":"Q1070249$7F7929AE-93DF-407F-B777-891B063D18F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00bad41aba828d2a748e12b72d53a65b7d10ff28","datavalue":{"value":{"entity-type":"item","numeric-id":2279271,"id":"Q2279271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72373a7fe79bf9b3cd9c7e1024350f277d1f3691","datavalue":{"value":{"amount":"+0.792621910572052","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":"Q1070249$1BDB823C-74AC-450A-BA68-E1A8D2303E40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"950e78328b1412029800caecf299475de934874a","datavalue":{"value":{"entity-type":"item","numeric-id":3035328,"id":"Q3035328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fe69d707e16ac4e080a477a8e66583803d54080","datavalue":{"value":{"amount":"+0.7844160795211792","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":"Q1070249$A0FB9DE3-B3FF-41EC-AFD5-6C9C35518BB1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\(K i\\)-covers. I: Complexity and polytopes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/%5C(K_i%5C)-covers._I:_Complexity_and_polytopes"}}}}}