{"entities":{"Q3010425":{"pageid":3021149,"ns":120,"title":"Item:Q3010425","lastrevid":51284276,"modified":"2026-01-17T14:37:19Z","type":"item","id":"Q3010425","labels":{"en":{"language":"en","value":"Switching to hedgehog-free graphs is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5916985"}},"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":"Q3010425$478FF48B-7175-407D-86B9-A7297CAFEC7D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5b6948e8f01cfe205ad63b43685586a0e1c59c15","datavalue":{"value":{"text":"Switching to Hedgehog-Free Graphs Is NP-Complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3010425$F8A24C28-AB8C-45FA-B995-40D9AC61375B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1782ed4262e4de14165bb1b75144cf811e705baa","datavalue":{"value":"1331.68092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3010425$5172668E-7B95-4FEB-BB79-A3F50B47A163","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0b9febfaeac43abe8f671259a32d59f3ffb1c95f","datavalue":{"value":"10.1007/978-3-642-20877-5_45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3010425$4CB42E32-76E4-44A3-BD71-99197087F696","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba44d81108b51c5e74dc72de0b9e3e5a20a1b0f0","datavalue":{"value":{"entity-type":"item","numeric-id":354440,"id":"Q354440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$7D0BA629-2D4F-44B5-A62B-BFEA1400E735","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$41B7DB09-34B3-4BE4-9270-306438B047FB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fd5c974ae982856259c10daa0aea2556c9e24f8d","datavalue":{"value":{"time":"+2011-07-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3010425$FC8EFA5E-746D-41F2-950D-638724F33B35","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3010425$34F282DE-995B-4B8E-8BD6-541BD6792D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3010425$ABD07E98-FC16-4324-A3D8-B8DEDB970355","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1cef36ce52e651b7aaf109f104c5ab4db588e5db","datavalue":{"value":"5916985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3010425$5FF19600-75C3-4A7B-97B9-98C774C403B2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05a7ac7aa0db02c53337f3b60292b8e930a7c388","datavalue":{"value":"Seidel's switching","type":"string"},"datatype":"string"},"type":"statement","id":"Q3010425$E809AFBC-C95B-4642-AC8F-184FDBEA4272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4be4c17b50a684952b6fa0c0a0a43b10f7746c4c","datavalue":{"value":"\\(H\\)-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q3010425$ECBF8CAF-648B-4195-B11F-8299174EF6A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3010425$DA1EA857-85E1-4C46-A9E3-765DC6978AE7","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":"Q3010425$686540D0-8008-48A4-A863-0B785EE32259","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ef9d70ccca66016da66bce3674497cf01ff8bd64","datavalue":{"value":"https://doi.org/10.1007/978-3-642-20877-5_45","type":"string"},"datatype":"url"},"type":"statement","id":"Q3010425$1B74714F-5DFB-41EF-8BA0-3D6D33AC6E0C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"14be7943536dbfccf01b99a41123fa705989b180","datavalue":{"value":"W1523756999","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3010425$9FC37258-41E9-45B4-B1A7-29D0BEE8D095","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"feba5d34b53b49c8564d122389830803f03e06c9","datavalue":{"value":{"entity-type":"item","numeric-id":294726,"id":"Q294726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$7B3AB013-2C2A-49F8-935F-1974B713D631","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7765ac06be3d3b89808932d5c166463362887293","datavalue":{"value":{"entity-type":"item","numeric-id":4502805,"id":"Q4502805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$55D73D42-D1E3-42B3-BD97-7B2009322099","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":"Q3010425$9312AA21-259A-4509-A9DF-205E1B9DCF0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"480570b028fb41d5998b832da52e5cfe143f906b","datavalue":{"value":{"entity-type":"item","numeric-id":4438776,"id":"Q4438776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$2B8DE894-707E-49F1-B2C5-CCD49BEC00A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0415202f47c71bb01fdf9479aecfe1915250d582","datavalue":{"value":{"entity-type":"item","numeric-id":1924124,"id":"Q1924124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$C4A6C9A5-0B1C-49E2-8A03-4E7331B4AE81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d808437cb510bfa585c7ac5cf20e7af7c5ba691f","datavalue":{"value":{"entity-type":"item","numeric-id":5967036,"id":"Q5967036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$0AB10AF1-7A98-44D6-B031-B7AD7FB7105A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53663a9ef488f814bd96dc04d758cc712ca5b4c2","datavalue":{"value":{"entity-type":"item","numeric-id":3540412,"id":"Q3540412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$D1224429-0401-4787-9D2D-7ECA1A070434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61a140f9a2efc67b1206bc93ee19916ba6fbf127","datavalue":{"value":{"entity-type":"item","numeric-id":4027169,"id":"Q4027169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$46018DC5-78E0-4782-9245-0BAE62C69DF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"769e8f0455f5eff74817b7d089025e1f2d8fbd8c","datavalue":{"value":{"entity-type":"item","numeric-id":5902530,"id":"Q5902530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$82372746-1AD9-4794-B89A-10EA93F81FB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98349cbaf9ed01640aad1951f4b9713b03f795c2","datavalue":{"value":{"entity-type":"item","numeric-id":3439330,"id":"Q3439330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$B5932E19-5271-4ABE-80C4-6C0F040E48AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e6893667cf1b0b0d2b50628b9a0ea2df7382aa1","datavalue":{"value":{"entity-type":"item","numeric-id":4745855,"id":"Q4745855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$A6C24A57-84CF-404E-BEA8-BA7F87EF5071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e07c2bcc6cf58baea2e2ef91d951530c704a2366","datavalue":{"value":{"entity-type":"item","numeric-id":4065580,"id":"Q4065580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$CC3B859D-50CE-4FB8-828E-CD987F285B6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdf0f787206ca5144e081089acc9c435376d77aa","datavalue":{"value":{"entity-type":"item","numeric-id":4887747,"id":"Q4887747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3010425$E1878489-6F58-437A-9475-98A3EB0A9FBB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e0619c5dd7c51dc7360e0421d83d86a276ab75b","datavalue":{"value":{"entity-type":"item","numeric-id":5417832,"id":"Q5417832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"313822c43ccf43839ab6f63cd14eb2a48fcdcdde","datavalue":{"value":{"amount":"+0.8745516538619995","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":"Q3010425$F3445EDE-D209-453C-A680-6B776F4AF435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6d3516ccbe925a117df55e3ec8a82fd597c6b52","datavalue":{"value":{"entity-type":"item","numeric-id":3540412,"id":"Q3540412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e28adc072749fe358465158548b5091b61237546","datavalue":{"value":{"amount":"+0.8410667777061462","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":"Q3010425$568E1265-73C1-4830-BBF2-F4DBC4D9F210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d4a5a7b1fa1b12e2e6cda95796091590a11ba39","datavalue":{"value":{"entity-type":"item","numeric-id":2817858,"id":"Q2817858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5eaa5cf78bb0e9ca2867a8e9dcbdfa5d883a33b","datavalue":{"value":{"amount":"+0.8063568472862244","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":"Q3010425$FBC3A912-5372-4D93-9C2A-FAD31169E68B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df4afb034bece778a605c9e9cad23c6e7339f561","datavalue":{"value":{"entity-type":"item","numeric-id":5346539,"id":"Q5346539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be72ef00f24bcd1a22a83d2064b0e8e8992b76e2","datavalue":{"value":{"amount":"+0.7632335424423218","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":"Q3010425$68877C03-E2F0-46ED-A293-FC2641E73435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4667b740dd09dd853f5ef8a230f6740c21352a12","datavalue":{"value":{"entity-type":"item","numeric-id":4027169,"id":"Q4027169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d17a1b0b815183548f24a3fc9c85eb59f3c1221","datavalue":{"value":{"amount":"+0.7620530724525452","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":"Q3010425$E2B64DAD-D638-4EDC-AA6F-FA893CE7E75D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3010425","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3010425"}}}}}