{"entities":{"Q1853132":{"pageid":1863874,"ns":120,"title":"Item:Q1853132","lastrevid":48034165,"modified":"2026-01-03T10:36:49Z","type":"item","id":"Q1853132","labels":{"en":{"language":"en","value":"Packing triangles in bounded degree graphs."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856472"}},"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":"Q1853132$6577F9B2-3AC0-420B-9090-A4D55F0F26C4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f15c420be3eba8ac34010b585721fc73a11b72ba","datavalue":{"value":{"text":"Packing triangles in bounded degree graphs.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853132$3064FDA1-EBD0-434F-AC6D-8EFDD168F378","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"40d0dd5f0add68fe3ecb71d6538ac0ff903bbc99","datavalue":{"value":"1042.68087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853132$D80E111F-6167-40CC-AF16-2A6C353FF174","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"28e28f055dbc27e648d83e3f271c86001c4724fb","datavalue":{"value":"10.1016/S0020-0190(02)00274-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853132$58C050EE-61A8-4DCA-BF65-AA34711C670B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"968995b09590014f0126da139a2774b9b9395236","datavalue":{"value":{"entity-type":"item","numeric-id":181211,"id":"Q181211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$803C3290-8A8C-4FC7-B2CA-D7EF417080C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"186bb8da4d9a21e884eff28e3a0bd8547b44ac9e","datavalue":{"value":{"entity-type":"item","numeric-id":168651,"id":"Q168651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$7CB8EEB1-EC02-4553-86FB-CE38379BBEEB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$47A47F22-E1DE-48FB-9B33-BD28F2E19B49","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853132$9D249483-A561-49FD-866F-9BFAD842FE0E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3a53a97dd08b556ca8f642fa802bd4ec002a2275","datavalue":{"value":"We consider the two problems of finding the maximum number of node disjoint triangles and edge disjoint triangles in an undirected graph. We show that the first (respectively second) problem is polynomially solvable if the maximum degree of the input graph is at most \\(3\\) (respectively \\(4),\\) whereas it is APX-hard for general graphs and NP-hard for planar graphs if the maximum degree is \\(4\\) (respectively \\(5)\\) or more.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853132$1E801695-8C2B-48B9-A72A-CAAEB7D62669","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853132$BAFEB84B-378C-4974-81B2-D0229E32CB8E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9eb82ef23bb8c618b23eece600b74a931dc74410","datavalue":{"value":"1856472","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853132$4FC56501-1FEF-48C1-A152-8E023FF089AD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0d63d20553e3f0df47debe226d13ac41a081351","datavalue":{"value":"Packing triangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853132$BD8076E9-7E73-48D1-B97D-0465B9114A0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e00ce5c2af8de199b95bd8caa7871ee08690a54","datavalue":{"value":"Polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853132$C9EE54DC-C23B-45D8-B247-8F5B2C907689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c562c36759035eb361c19aeaefa854e6a2248a18","datavalue":{"value":"APX-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853132$B6304B6B-6A9B-4E00-9BAB-720995AF253B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79649971f82e05400ec7b69d88c87623d70fb310","datavalue":{"value":"Planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853132$6AF814A7-647D-4215-8A67-6BF4405BA307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853132$CAF0AC59-8FCE-469A-8D82-8F7206CA0224","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":"Q1853132$C3A388E0-100A-4CF5-8246-B9795184DA0E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5aa2a1ac4e864d41c30b8a828a68a91d18d8ecae","datavalue":{"value":{"entity-type":"item","numeric-id":4258216,"id":"Q4258216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$D6AFA661-9D3F-4A52-8A5D-751A85FC05D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd386990ad28d7631b1993101e8123a7da1e3fe9","datavalue":{"value":{"entity-type":"item","numeric-id":4877518,"id":"Q4877518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$0D6AAE66-F16C-454B-BC55-F823861C4B88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5175a0c52543e9a486983cedbc3846a9743cc3a","datavalue":{"value":{"entity-type":"item","numeric-id":4299299,"id":"Q4299299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$C9796C7D-1BF0-4412-A540-74CF8155B398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d2a28d4576ca5d07a67d4189c52a283c7dfb9a","datavalue":{"value":{"entity-type":"item","numeric-id":4796199,"id":"Q4796199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$ABDB34B2-B9D3-4D43-8323-98169B4795CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$AEF0FF02-82B5-4CC1-8E78-B960FB652DEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff5e201c2b579b8c70d76c6408c175e8ca744357","datavalue":{"value":{"entity-type":"item","numeric-id":3922182,"id":"Q3922182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$E33BD47E-608B-4057-A481-5DDFD5BB5985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c7a3a168ec043e3817d8a3edf6d51bc4bd9e3fa","datavalue":{"value":{"entity-type":"item","numeric-id":3360178,"id":"Q3360178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$5D5617E9-BB5F-4AFC-9067-86E5011C1683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"429924f0ddd3bc1c7dc54a3226f108e3ebc2b532","datavalue":{"value":{"entity-type":"item","numeric-id":922700,"id":"Q922700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$78B26E25-4034-4D47-BB76-C1C340B9B255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"176f92be0a5c8084cbea32a162c15c6e5a582bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3936195,"id":"Q3936195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$D63C1534-EAE0-414A-842E-1F547BBA25CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ada71f343b2168554ef3d8e68058bb18dbed1fd2","datavalue":{"value":{"entity-type":"item","numeric-id":1139605,"id":"Q1139605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853132$CCF9EF2D-AAC2-4D0C-B62E-B8EB60EE33E8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d6bfc4490efccd3c7c0c87631e3b1e4861ded3c3","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(02)00274-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1853132$D7DEA46A-52F0-4B95-92C7-CE355B080C41","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"069b673afaea68103ad855f2ce913ac6f2c99825","datavalue":{"value":"W1969483202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853132$91D98FD8-729C-47F3-9E75-B11F34474E89","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2800e6aedaf70777e9d499f0d3f94e620c822976","datavalue":{"value":{"entity-type":"item","numeric-id":2476287,"id":"Q2476287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"435ee509d8b8c95f80be6abab220a4d9aa90a4cf","datavalue":{"value":{"amount":"+0.8609972596168518","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":"Q1853132$45D8483F-603E-498F-81C2-3C3488911984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fdfcc66bbfe454ba83494290995ea5f32dc9496","datavalue":{"value":{"entity-type":"item","numeric-id":3576699,"id":"Q3576699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a39c7d370e7ba0178155b4939337a05ff612999f","datavalue":{"value":{"amount":"+0.8608022928237915","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":"Q1853132$70434C20-2F20-4F4D-A742-69EF3D529BF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fe031fd170d087fd465d45d20c769de5ac05b69","datavalue":{"value":{"entity-type":"item","numeric-id":2392247,"id":"Q2392247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"502fcf604ff99f88d4d9934768d0eada5a0158cd","datavalue":{"value":{"amount":"+0.8411416411399841","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":"Q1853132$2EB0F373-EC5B-4466-BF59-C2D99EC34B4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4962bec090bd6bb71c6e23d6450da79d5b200ad1","datavalue":{"value":{"entity-type":"item","numeric-id":2583122,"id":"Q2583122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64a6faabc2da2210bb21c071b24724a664e8bea5","datavalue":{"value":{"amount":"+0.8385890126228333","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":"Q1853132$500521D1-234C-4955-8FDA-BBAD98B65FFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc13ca210af3af8ecb500261087833aab7268087","datavalue":{"value":{"entity-type":"item","numeric-id":4232775,"id":"Q4232775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac5b08c4083157401122527291228a54094ecf74","datavalue":{"value":{"amount":"+0.8379368185997009","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":"Q1853132$6F1DEA63-BE67-456F-A081-89DB75161093","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1853132","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1853132"}}}}}