{"entities":{"Q794164":{"pageid":796012,"ns":120,"title":"Item:Q794164","lastrevid":48710833,"modified":"2026-01-05T16:43:38Z","type":"item","id":"Q794164","labels":{"en":{"language":"en","value":"Edge-contraction problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3858409"}},"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":"Q794164$B040F3C9-75A0-419A-9730-E529FD564CBC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"77c5c8b157a01670ee9a9494ed5d8fa67642d0b9","datavalue":{"value":{"text":"Edge-contraction problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q794164$57452573-1F60-4A14-971F-57D30FA0B711","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cc6df339d3bff6f6ce0572b584023a50ac64c2a6","datavalue":{"value":"0539.68034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794164$DDFBA053-1AFA-41BF-818D-BE659197A96A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a886ecc6e9b8ef346b6529fbd2cd9889943484a2","datavalue":{"value":"10.1016/0022-0000(83)90012-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794164$6E6BEEA0-9128-4D0E-8A94-392CF0126878","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0608c28dd6e3edb1ad2e60313b9ab4c48668656b","datavalue":{"value":{"entity-type":"item","numeric-id":406636,"id":"Q406636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$46683069-1395-4216-924D-B4DB023A9D17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8b922df3f14edd5da4aa5b2a1deeba044dc54ec1","datavalue":{"value":{"entity-type":"item","numeric-id":751324,"id":"Q751324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$286F9314-B35B-4BD6-979B-73ACC02FC13A","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":"Q794164$D7BF55F7-B9D1-4AC0-B762-03E363145EDD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q794164$F1C6E27C-6A00-42AA-BAFF-1B9C85E72E24","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"debf29328bd2c3bf48dce173895c3fc75f6101c5","datavalue":{"value":"Der Artikel stellt einen Beitrag zur Systematisierung der Beweise auf NP- Vollst\u00e4ndigkeit dar. Das folgende Kantenkontraktionsproblem f\u00fcr Graphen ohne Schlingen und Mehrfachkanten wird untersucht: \\(P_{EC}(\\pi):\\) Gegeben sei ein einfacher Graph sowie eine ganze Zahl k. Gibt es eine Kantenteilmenge S mit \\(| S| =k\\), so da\u00df der durch Kontraktion aller Kanten von S entstehende Graph G/S die Eigenschaft \\(\\pi\\) hat?    Die Autoren geben einen Beweis f\u00fcr die NP-Vollst\u00e4ndigkeit dieses Problems an, der sich auf verschiedene Klassen von Eigenschaften \\(\\pi\\) anwenden l\u00e4\u00dft. Explizit werden zwei F\u00e4lle behandelt: (1) \\(\\pi\\) nichttrivial f\u00fcr zusammenh\u00e4ngende Graphen, heredit\u00e4r auf Kontraktionen, durch den assoziierten einfachen Graphen bestimmt, ebenso durch die 2-Komponenten des Graphen bestimmt; (2) \\(\\pi\\) nichttrivial f\u00fcr zusammenh\u00e4ngende Graphen, heredit\u00e4r auf Kontraktionen, f\u00fcr alle Graphen mit h\u00f6chstens drei Knoten erf\u00fcllt, durch die 3- Komponenten des Graphen bestimmt.","type":"string"},"datatype":"string"},"type":"statement","id":"Q794164$9F0F50E3-329F-4234-84AA-DA44ABE51CC9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794164$D87B13D0-A822-4F38-987B-838DC0FBC441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794164$8C611B93-8CE4-4E9F-ACFF-65DE53FAC4F2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3f7b9af718e6a3a09fd3e574ffd509d053734977","datavalue":{"value":"3858409","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794164$E836C2CA-D477-4417-A178-A80C23C229AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bacd7d1969a2420ea596599d89a68b65893ca2d7","datavalue":{"value":"edge-contraction problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q794164$2DDD67E8-F7EE-4945-ACCC-209DE90CEE0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q794164$EC8F3BE1-4167-431C-A520-BA11A29B5C7C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a201a8779f110985d707176577b688d9a6216e1","datavalue":{"value":{"entity-type":"item","numeric-id":649735,"id":"Q649735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$6D526BCC-D0A4-4A4B-BFF8-8DFEC7AD856D","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":"Q794164$3955FC1F-6C6D-4703-875B-EF728FD8A0EA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c02dd876d0a9046cc6e222a8a4822cc0729024aa","datavalue":{"value":"https://doi.org/10.1016/0022-0000(83)90012-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q794164$5D861150-642D-49A6-809D-A93A3880C242","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c1d957db02741ab5a6968d3f5d8dbcb1c0cf42a7","datavalue":{"value":"W2062347470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q794164$4B3196B6-CB5F-42EF-B5F5-D3FC737ADEEE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$DB36C102-2092-4BAC-AE71-EA81A77A2DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef757ecac8e00102e8fe2d81d7657ee3391ff698","datavalue":{"value":{"entity-type":"item","numeric-id":4138187,"id":"Q4138187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$A83A2CF1-99E6-4B77-AC36-02FA024D0436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4b70304ff30a1256f46103099164d048b244266","datavalue":{"value":{"entity-type":"item","numeric-id":4766817,"id":"Q4766817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$31E6229B-4344-4F57-B94F-0F5722C4F806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$6FEF5BAC-2C18-4C74-9C0D-E84713E30C68","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":"Q794164$30BFD07B-12FF-4DAF-9500-A7E0CBCD1942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849849a8734e624cdd488bd27603bced49d0bfd9","datavalue":{"value":{"entity-type":"item","numeric-id":4083698,"id":"Q4083698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$637D3FA9-9517-4D9F-A5C7-BB1070DE2BC2","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":"Q794164$77343553-6C7E-491F-8CFD-46D981109C74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$FC942BB8-52C1-4734-A96A-4715C1D35E29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$3BBF32AE-AF31-42F2-993D-39253FE9ED90","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":"Q794164$DB2D09C1-B14D-4ED8-8327-01FBCA60FDB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ae06ace3264ebdef666fd198a2d1441400a748e","datavalue":{"value":{"entity-type":"item","numeric-id":4087195,"id":"Q4087195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$9D1A2D07-994E-4B3E-9DB9-BC91739C5122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c9291d93c646837901323366831f6909a635320","datavalue":{"value":{"entity-type":"item","numeric-id":3856812,"id":"Q3856812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$3A5A6964-356C-41D0-AE1D-1A698D0B04D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fb0e137e137d67cf21dfa60890f8ec3ac67746d","datavalue":{"value":{"entity-type":"item","numeric-id":5402566,"id":"Q5402566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$3FF6CF30-A3EC-4BDD-8604-8D6B03745CBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a7a6c6b8ed22abfff754835104aaed55a1d4a80","datavalue":{"value":{"entity-type":"item","numeric-id":1140988,"id":"Q1140988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$E61CFB7B-6D07-4FB8-A7FB-4C4E8385983D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab905d27922a85af616443e1769a1850cb9248b6","datavalue":{"value":{"entity-type":"item","numeric-id":5524326,"id":"Q5524326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$4E17D6A3-DF6E-4ADF-9BEC-993D856938CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f6e21f081b18e8c1b37c600fa32ad6a2a06b4c0","datavalue":{"value":{"entity-type":"item","numeric-id":1146698,"id":"Q1146698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$084A9F3D-AA8D-4F2E-B8B4-5A20953152AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53931acda4d1de6fffc8c785b472a64b77dbbda9","datavalue":{"value":{"entity-type":"item","numeric-id":5402565,"id":"Q5402565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$D2DCBF2D-82F4-461A-97F5-D529DAD03A64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f553c8f59e26fce96d1650fc4043c8eb59e4441","datavalue":{"value":{"entity-type":"item","numeric-id":3854626,"id":"Q3854626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$92C4E90F-B1DC-43C0-B1C1-4E35F93A37C9","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":"Q794164$68AF1501-489C-4028-AE35-3EE912EBBFF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dca477d65333d3d53a4667c44899b3e70251aa0","datavalue":{"value":{"entity-type":"item","numeric-id":3921261,"id":"Q3921261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q794164$92644C95-7445-4D74-A515-4CFD84167DB8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8c835c4c8a305a0354c09fff59b3881b3f89fce","datavalue":{"value":{"entity-type":"item","numeric-id":3739139,"id":"Q3739139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b92a8298ef5ee8371d31eb994e5223307e8e0451","datavalue":{"value":{"amount":"+0.8206492066383362","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":"Q794164$8F9EB2EA-C9CF-4623-A876-B1DB60EBB1BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2011db3b1eca8772a63e9668e8717dab56be8819","datavalue":{"value":{"entity-type":"item","numeric-id":3507648,"id":"Q3507648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df6bfe8da52a84120cf800b6b0c744758da67a54","datavalue":{"value":{"amount":"+0.7995311617851257","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":"Q794164$703AF695-BFC6-4D95-8EE9-015AD828FA64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f88a0516d5d6ada66e5398a3cb379a21fd1f8a01","datavalue":{"value":{"entity-type":"item","numeric-id":2912744,"id":"Q2912744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8b9f3eaf194c25ded288710f037e36892f95bd2","datavalue":{"value":{"amount":"+0.78572678565979","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":"Q794164$323F4BC1-0059-4C7A-9739-6357FE296274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc2e07e3be6ec2ad75cae4d8dee24ef8583531a5","datavalue":{"value":{"entity-type":"item","numeric-id":5402565,"id":"Q5402565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e05962a9180f5b38d57b0328f5f8d1e640dfc22c","datavalue":{"value":{"amount":"+0.785006046295166","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":"Q794164$CA62418D-DB18-4126-A593-E35CB7F0C3DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b3a1dbb6551d8737a27d503e2e131681af3990d","datavalue":{"value":{"entity-type":"item","numeric-id":1945931,"id":"Q1945931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a71ef1a977ce4637ca021361f03f8c7f93623d23","datavalue":{"value":{"amount":"+0.7830797433853149","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":"Q794164$C8FEAD38-EEB5-41FB-AF57-382D7E91F647","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:794164","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:794164"}}}}}