{"entities":{"Q2575831":{"pageid":2586574,"ns":120,"title":"Item:Q2575831","lastrevid":72810483,"modified":"2026-04-14T08:00:31Z","type":"item","id":"Q2575831","labels":{"en":{"language":"en","value":"A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2235952"}},"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":"Q2575831$B6F61A91-D445-4A0F-AD52-392E2F21BBC3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dfbc35cf0c36e5c7fa662e2001ed9a8bd91943b1","datavalue":{"value":{"text":"A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2575831$D7EEF729-BAAA-4CB9-A9D5-E6D7C7AF3923","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"180aac8026ef1d7c3f85b75791f2e86b617870cb","datavalue":{"value":"1101.68613","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2575831$26D8E3BD-7326-4540-B7D9-B3C421D0547C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"141e9b6dd3fae00505c999d51fba91d7c475c99c","datavalue":{"value":{"entity-type":"item","numeric-id":378211,"id":"Q378211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$B8BE90C8-F773-4750-91AB-2BFD41D116DB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$1D7DB0D7-540A-425B-9654-6F3986199E99","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0a6b2dab0c1a850c148e524dd23e597ec7eb88d7","datavalue":{"value":{"time":"+2005-12-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2575831$93576670-79D9-4D24-8CA5-8429B1985A00","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2575831$6D3BC6B5-ECBB-489E-8769-54E90F5194C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2575831$BEF26141-56A9-442E-8AC2-3C16D975B05A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"665e2b5b6318dcd7d2201f4137db502765d76803","datavalue":{"value":"2235952","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2575831$312D6508-83BE-4331-8233-C7CE1E82C2C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da67da54e89e7c80f20f3f95c3ceec18bb927753","datavalue":{"value":"Computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2575831$AFDD641D-2C0B-4C5B-9955-091CCF92A088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a72e8bc0923282005bce6a398b98c6852da0f38","datavalue":{"value":"Graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2575831$8B422ECE-95EB-430D-831B-1526B792270A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e4e9dcec4e9a1525f3278304b911a868c1ee465","datavalue":{"value":"Colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2575831$5C0D0F97-256B-4F55-BF01-C29B90C98384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6eb287b1754b756e31b13d00c41c136f6cea1ec8","datavalue":{"value":"Homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q2575831$8C09764D-6821-40E6-8133-D57DD2B0FF08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a696c66c1915beddc30a307a20d60ed8de05feb","datavalue":{"value":"Retraction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2575831$4AADDC9D-84CA-45E8-97BB-2CA9A6437A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11485e5eb81b8ea449f6d90231fcf5cbfab058da","datavalue":{"value":"Compaction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2575831$94A3C07B-2ABE-4165-BBA1-2632CB750491","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71c995465fb2b12d9ccc966c06387f7eb90c2438","datavalue":{"value":"Partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2575831$EEF541F3-8FBB-4D2C-8EC4-81C1DC75017F","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":"Q2575831$4D0938F2-7719-4436-8146-873B41D58C42","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"360e6ab4d92ba150bbf64eaf1af4240b0dcaee42","datavalue":{"value":"https://doi.org/10.1016/j.jcss.2004.07.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q2575831$E21539BC-BB87-4866-AAAB-FC2CF7DAA7C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fd6c99b456467407c270ce245b813db9c13a231c","datavalue":{"value":"W2051028069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2575831$1AE5F2D3-01FD-4D74-B66A-0BAF977A44B6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3090ad0bfc78c33c00c689498eea4d7452c40f4a","datavalue":{"value":{"entity-type":"item","numeric-id":1820174,"id":"Q1820174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$FE9CC63C-9A6F-4B74-849B-47357E5D53FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf653ca76c03edd57ac2f36a85ddf24e5b51f007","datavalue":{"value":{"entity-type":"item","numeric-id":686243,"id":"Q686243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$33262C95-072D-4224-BA54-20013F55A25C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$CAAE512A-378C-4A1F-8CCD-D22D171536B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75d4076d4897ab3cc8f6948af493950051b74467","datavalue":{"value":{"entity-type":"item","numeric-id":1127870,"id":"Q1127870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$3DB1E584-6FE6-4FB1-A829-2909AAD7CBD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72636d83503e896e571d6f2c09be11cb7bc2ca51","datavalue":{"value":{"entity-type":"item","numeric-id":1977431,"id":"Q1977431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$CF86B350-D7C1-46B2-9823-1B4214862216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a72e9d690a10e1ad1169c20d997337685ab0dc4","datavalue":{"value":{"entity-type":"item","numeric-id":2819579,"id":"Q2819579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$FF2F396E-0BB7-4A34-9060-0F9A91191DDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1478288fbfb8ca77d6855c6c3ca4dc8072bc6c49","datavalue":{"value":{"entity-type":"item","numeric-id":4443101,"id":"Q4443101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$BEE7BA47-E43B-4D12-9A9E-FB1A37D1C6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7aaa9bb137fa2b1d06177861fbdb923853dbb86","datavalue":{"value":{"entity-type":"item","numeric-id":5248532,"id":"Q5248532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$DE2CDF48-C218-494C-B103-E1B3C6606BA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5c6061c3f6daf7454d0e9c58daef6f441530aa","datavalue":{"value":{"entity-type":"item","numeric-id":4210136,"id":"Q4210136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$854980B3-2C84-417E-92E3-E8FC7FB6A173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a0a8e4ccae21ea52906e2c227811922501b04ce","datavalue":{"value":{"entity-type":"item","numeric-id":4110937,"id":"Q4110937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$8E2B7A76-0B00-49C7-B82D-A28609A4A38C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$C4C89C8C-70A2-476F-ADC2-970617B1BC93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d763fce60094f944e300d72a35c965d018e23427","datavalue":{"value":{"entity-type":"item","numeric-id":4049082,"id":"Q4049082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$28FFEF3B-57AE-438B-84E0-A75B3709DBF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67d48c486909bc11592eb260f76156b9f2729613","datavalue":{"value":{"entity-type":"item","numeric-id":3941434,"id":"Q3941434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$3E551C89-31B8-4743-BE02-65030EA7C3B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec165abc7ade014841f417bcba31a647c17e0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$81400288-3CD2-47D6-905F-65FC41A848EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d02d74650476f02cec956b43ba91c01ec65b6fa6","datavalue":{"value":{"entity-type":"item","numeric-id":3030858,"id":"Q3030858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$A0E97105-3AFB-445B-A3BC-9617D55DCDC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6de6567d0855af78dff6f0d702d482dc3949bf8","datavalue":{"value":{"entity-type":"item","numeric-id":3201104,"id":"Q3201104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$6A1D0A1D-81B0-405D-812C-4CA2583ADCD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32669c9303b6fcfce30a867e0ec9585dd818044e","datavalue":{"value":{"entity-type":"item","numeric-id":3878752,"id":"Q3878752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$DD6B22CC-F0F9-476B-9318-519CD5137B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c26050d258b183673b275b45306c6038c52bc7a3","datavalue":{"value":{"entity-type":"item","numeric-id":1155066,"id":"Q1155066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$BC2126EB-EFEA-4DB9-9E56-FACD96CF5036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1621ff3cf2a04da7835881703df769ea6e795c16","datavalue":{"value":{"entity-type":"item","numeric-id":3869378,"id":"Q3869378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$CDA68942-693E-4CE6-9D7A-95EC1C895666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4095f1f6405e946721b10017e14eb123a400db18","datavalue":{"value":{"entity-type":"item","numeric-id":3994353,"id":"Q3994353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$0F39918D-5777-4801-ADEA-923EA1FA1E75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3477a7a323372dbdece609d5e2dc8aec634990b9","datavalue":{"value":{"entity-type":"item","numeric-id":1076682,"id":"Q1076682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$0E3C58B4-621B-4D0B-8A91-F2D3121EF5E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"611617bc0f0ebb24f0f9f754815d9db4c74eafbe","datavalue":{"value":{"entity-type":"item","numeric-id":4252439,"id":"Q4252439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$7A7831E7-D270-4A01-85B1-744720BF2142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52fe3e8487c6be927242abe9f379d11adec507ae","datavalue":{"value":{"entity-type":"item","numeric-id":4706192,"id":"Q4706192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$227AF4CE-22B6-4617-BBB8-B5DACAEB4B0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a906913b8285a5af87ae5c96df4f54b7e0846e6e","datavalue":{"value":{"entity-type":"item","numeric-id":596309,"id":"Q596309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$82D1F634-12D7-428A-A188-B4DFC5C0C5BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af8aa8e69b984263d0612021c813b1cc15408bf1","datavalue":{"value":{"entity-type":"item","numeric-id":4651492,"id":"Q4651492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$D83A5552-C038-4F81-A9FE-2792C83BF2E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ce50702bda0c9a1126e7a286a023ebb181a03d1","datavalue":{"value":{"entity-type":"item","numeric-id":4681200,"id":"Q4681200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2575831$27C57DE0-8494-4850-A08B-071BCFC99105","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"089e3361ad5bc3150320cb4cdb3d8bab147e816c","datavalue":{"value":"10.1016/J.JCSS.2004.07.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2575831$D896018C-4BA8-4E86-A639-B58246799B69","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"feccca5e9cf9177c0045fdd4aa873f5f741d4723","datavalue":{"value":{"entity-type":"item","numeric-id":4681200,"id":"Q4681200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5c5d91458ff5dabefe8b90d851333af5cbaa9b9","datavalue":{"value":{"amount":"+0.9623849987983704","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":"Q2575831$2F97FE86-3DB2-4B14-9715-1B4A15E3D2CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c63eabd2f4f0bde934c1824b5189827160a7ad2a","datavalue":{"value":{"entity-type":"item","numeric-id":5915913,"id":"Q5915913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca4428f0eec2d0ae7ec003c1346e27420d853329","datavalue":{"value":{"amount":"+0.9323290586471558","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":"Q2575831$0C49A4DD-5BE4-46EF-9315-52AD3EDFF742","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7ef13b9c34211b2f260e2a6edfcc4aad97518ef","datavalue":{"value":{"entity-type":"item","numeric-id":5915645,"id":"Q5915645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05216af1624dead8925df6324eb9ae44bae36aba","datavalue":{"value":{"amount":"+0.9306063652038574","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":"Q2575831$581607D7-9D2D-4F67-9EA1-57DBD19FAF11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f97b09331df7af494d83d7d0b748f3361ec76f8b","datavalue":{"value":{"entity-type":"item","numeric-id":4651492,"id":"Q4651492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6759f2638295e63340c4171f4aad90e3521df2bf","datavalue":{"value":{"amount":"+0.8777697086334229","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":"Q2575831$9CC66BA5-DEE7-40C4-9EBD-AE1905B247AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"903fc37b13c08122590c8bc8523b2d0a79d53c6a","datavalue":{"value":{"entity-type":"item","numeric-id":378212,"id":"Q378212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e2604009b324e15341f953ebd03203c3e70cc9d","datavalue":{"value":{"amount":"+0.8308380842208862","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":"Q2575831$D1115695-61C6-43AD-A52D-877B72B28737","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_complete_and_equal_computational_complexity_classification_of_compaction_and_retraction_to_all_graphs_with_at_most_four_vertices_and_some_general_results"}}}}}