{"entities":{"Q1059641":{"pageid":1061489,"ns":120,"title":"Item:Q1059641","lastrevid":66652203,"modified":"2026-04-12T11:34:11Z","type":"item","id":"Q1059641","labels":{"en":{"language":"en","value":"A note on the complexity of finding regular subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3904617"}},"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":"Q1059641$A547AF37-64EC-4657-A979-590D6B57D100","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"75c21e665a623d3400962196099381e129c086b6","datavalue":{"value":{"text":"A note on the complexity of finding regular subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1059641$E1261F59-07AF-4C8E-B17F-B45DE3E03D67","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"47ffe867b2e4115d30e775a66c3375f129dc4be8","datavalue":{"value":"0567.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059641$9329E6D3-D255-40AF-AEA6-4CBABBB5DBDF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"93f8a196d15258e96c0616d7954c84c27e2a2449","datavalue":{"value":"10.1016/0012-365X(84)90113-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059641$A239EA1B-0542-4F17-8035-8C1F47B337E1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4a120d6bb1cc9f6ec359898a7cc3913a78a488f","datavalue":{"value":{"entity-type":"item","numeric-id":222481,"id":"Q222481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059641$CED6BF28-153B-4EEA-B544-7FBF800A43EC","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":"Q1059641$26966936-AC88-451F-B1A2-96BB64335AC0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q1059641$C166BEC0-90DA-4B00-8CDD-DD8B346E8ADB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"42fdc99ddf234ba8a271c584d30b861e85849a1c","datavalue":{"value":"This is an interesting investigation on the algorithmic difficulty of detecting regular subgraphs in a given graph. The author proves a general theorem which states that, for a given graph G and an integer \\(r\\geq 3\\), the problem of deciding the existence of an r-regular subgraph of G is NP-complete. NP-completeness is proved by polynomial reduction of the known NP-complete problem ''exact cover by 3-sets'' to the new problem. Stronger results are then presented; these show that the r-regular subgraph problem remains NP-complete even when G is a bipartite or planar graph with given characteristics.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059641$E8CAAE2C-F568-4C8A-AC51-9284F9783B7E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059641$B5387FF5-F7FE-4956-B0F2-F7C023A7BB27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059641$C76EE030-AE92-44FE-AE28-4F7E7907BA71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059641$C8AFF46D-7253-4F96-8921-79D47E8DC5E8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ca46d76b71d29dad081e41fcd4313aa7e6529b3e","datavalue":{"value":"3904617","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1059641$A0463844-C0FF-4BA8-BDFB-148B75D09F02","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9543ea852bdf48f712e05f851b1bdaff3fcfb6bc","datavalue":{"value":"detecting regular subgraphs in a given graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059641$1C17EF17-648B-4F69-9AFA-12C6F7514428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1059641$C3BB0A5A-13FB-49F8-BF13-4FE41891133E","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":"Q1059641$0B95C7E6-A342-4174-9DC5-9E355E47E46C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa6b88d7c0c035ddcdc73a99f8a04d3f8ce9fbcc","datavalue":{"value":{"entity-type":"item","numeric-id":4187840,"id":"Q4187840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059641$3E0F0FCF-D352-426C-A766-10CBDB412FD8","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":"Q1059641$0CB0DE77-4B73-4E52-A87B-C3B6D99C8EFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d906f3c46833323d2760e1ae249eacc0a5d54bac","datavalue":{"value":{"entity-type":"item","numeric-id":5904287,"id":"Q5904287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059641$46EDA97A-924B-4069-9C91-CCFEC614B335","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":"Q1059641$CDC0F165-F23A-4A5C-98F2-642FF9C6E96C","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":"Q1059641$3225CEE5-777F-44A7-AC33-A10715069ABA","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":"Q1059641$F4E0688B-7155-40C3-8B22-7C122746E382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63ada53980e8d3e7e8a0a401742a431780860804","datavalue":{"value":{"entity-type":"item","numeric-id":5825672,"id":"Q5825672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059641$5DD16980-1145-4DAF-B1B5-FB2F9D641C62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"708ee3d6796034c1a9a52a76bd59ac1c0b194ed2","datavalue":{"value":{"entity-type":"item","numeric-id":3929767,"id":"Q3929767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059641$61211CEF-DFD2-45B4-9482-FC4B9007CA2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6ece3abee128cae96f66d5215a2ec594e85a3b4","datavalue":{"value":{"entity-type":"item","numeric-id":3960741,"id":"Q3960741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059641$419D0A37-C595-48A8-8852-985874EF2291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c80a69b6195da07678b4545abe9ce12891a5a11","datavalue":{"value":{"entity-type":"item","numeric-id":4750685,"id":"Q4750685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1059641$5ED9E631-4473-42C5-9717-1EE808FBA6D1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2739849794c5e5b2f7bf2df4ba46f90e8d647a2a","datavalue":{"value":{"entity-type":"item","numeric-id":4865472,"id":"Q4865472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de6b8c8590a5eade901de6d0974226f987c9357d","datavalue":{"value":{"amount":"+0.93350536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059641$E848F0AB-7449-4790-ABDB-7E1564F1C3CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40926ffb5939c4c787518a2f14704a7fe6e8b028","datavalue":{"value":{"entity-type":"item","numeric-id":912615,"id":"Q912615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1aae8eeab544c958ba09caf87bf14f4face2a80f","datavalue":{"value":{"amount":"+0.9272435","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059641$60085070-5C5E-4465-9BEF-DDFE34C7D8A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0b08d348dc92994edf80e39cec80628079708ce","datavalue":{"value":{"entity-type":"item","numeric-id":1026227,"id":"Q1026227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37270f3d0d297eec9cd40e2bdd81cc992c87ed1a","datavalue":{"value":{"amount":"+0.92210305","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059641$A6E5F830-C827-49DF-B955-41094A865663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd8dd1a41865d7f114a6546cab4870590f13335b","datavalue":{"value":{"entity-type":"item","numeric-id":967414,"id":"Q967414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b40cfd8a60b091bfb6e17ac8b9d61921e63fb3e","datavalue":{"value":{"amount":"+0.9181146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059641$38EA102D-B7B5-49E6-992D-ECDBFC6C6AE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd30d93907ee483ce82858f025ae4074b6d1ce4f","datavalue":{"value":{"entity-type":"item","numeric-id":4333456,"id":"Q4333456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11317ce2ea4a32569e80d9ae8c478ce0ee225812","datavalue":{"value":{"amount":"+0.91742456","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059641$524C64AF-81BC-4169-B20A-2D7A7A972246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87ff713b68d57474eda6aed4e6a2f6096af24b0d","datavalue":{"value":{"entity-type":"item","numeric-id":3688439,"id":"Q3688439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94a89ff213a67387b1c25ef2b4981ef3bd3fe1b5","datavalue":{"value":{"amount":"+0.9140905","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059641$580E305F-9B84-4AA9-8ADA-E2E67DB43064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce018cbd6c2ad923190dcb3865b5bdae9978c51a","datavalue":{"value":{"entity-type":"item","numeric-id":1923612,"id":"Q1923612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f23a27184c37ccfd23e1a68679d7ac2d6d663b0","datavalue":{"value":{"amount":"+0.91152483","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059641$44534D0E-DAF2-49D8-A3FC-95E111B91FC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09e7a554c64d5140988ccb2612b93baa55eef91a","datavalue":{"value":{"entity-type":"item","numeric-id":1175798,"id":"Q1175798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d511104ae42423a733701a2f3cabe03f693e44e4","datavalue":{"value":{"amount":"+0.9108486","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059641$EF14FC41-4186-4123-8F32-2F7AF22AD1A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad7a31751d2c74b1da59822af3f95dd19a9e4cd1","datavalue":{"value":{"entity-type":"item","numeric-id":401302,"id":"Q401302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b0f6a22fe8f766c962565053aa04d4e1f33f4ff","datavalue":{"value":{"amount":"+0.90986407","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059641$0BA5C5D4-835F-4099-B7B4-1BA0DD7B7F9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ff3e120ed57cd8b033d1682050b698433937ab4","datavalue":{"value":{"entity-type":"item","numeric-id":2842769,"id":"Q2842769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b0f6a22fe8f766c962565053aa04d4e1f33f4ff","datavalue":{"value":{"amount":"+0.90986407","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1059641$B75971A3-0B36-4826-A9D2-6720F6A4448E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on the complexity of finding regular subgraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_the_complexity_of_finding_regular_subgraphs"}}}}}