{"entities":{"Q1838829":{"pageid":1849571,"ns":120,"title":"Item:Q1838829","lastrevid":70962885,"modified":"2026-04-13T18:31:57Z","type":"item","id":"Q1838829","labels":{"en":{"language":"en","value":"On the NP-hardness of edge-deletion and -contraction problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3806934"}},"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":"Q1838829$F303E287-E663-4DC7-A107-DFEC9CEA4B89","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2192ed753974308f45814388ec8aecf0e5c9afed","datavalue":{"value":{"text":"On the NP-hardness of edge-deletion and -contraction problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1838829$5D2DDDFD-2DA2-4610-82B0-35A9218AA23C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bf172042357ff9fd4e9b95d7360c069910242045","datavalue":{"value":"0511.68028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1838829$ABAC9C4A-AAC3-468D-8E0A-4A619FCA27B4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"04b24fd04e0ec4cdb88846ede5beea5cf7fb11d2","datavalue":{"value":"10.1016/0166-218X(83)90101-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1838829$04BBF869-664D-441E-AD59-91EC40D2DA3B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1838829$335589E4-426E-40E5-90F8-0C94BA141D17","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1838829$F08B39C0-0B27-4354-B2BC-7AB77A71D7A4","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":"Q1838829$EE26AE06-1E94-449C-987A-CA487CE905EB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1838829$56B3DF7A-2114-4163-8E08-D77E2DE6F879","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d210eb2c1de4b4765264f140e13c2a25ec4da004","datavalue":{"value":"3806934","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1838829$330775C9-E505-4B07-A0E5-CD353C3E379E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e2847eefec0179e00a7eda84e333666b3de1a15","datavalue":{"value":"edge-deletion","type":"string"},"datatype":"string"},"type":"statement","id":"Q1838829$C4494FDE-91D3-468F-8529-E432037F9648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18d4a1de8298b0e2011afc19c3784981430ba74c","datavalue":{"value":"edge-contraction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1838829$925C1C31-2D18-4E51-9FD7-EE2F132B0B30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1838829$DB225AC4-DE75-4411-AA16-ACDFD2B562C9","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":"Q1838829$A08B6961-7566-4DE8-920A-FD7F9A230B41","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":"Q1838829$3DC3EAF3-98D1-4B68-A5D8-A62EF714AB92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1838829$85036CFE-0668-4500-93FF-BC4C9D29AF54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1838829$CCF10C37-1548-4A28-8853-0D3CC3016D09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1838829$76350DAF-36F3-4DB3-A874-B2D275C4F250","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":"Q1838829$1FF920A7-FA70-42AF-B6B4-25266E0399DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e65d73ae8ce50631a13a2e25599a048bc2eda73","datavalue":{"value":{"entity-type":"item","numeric-id":4158479,"id":"Q4158479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1838829$5EAA2FFF-8524-446F-8AB9-D7A5A0160119","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":"Q1838829$31FF9AE6-9E8D-4A93-B6EA-7333CC5E89B2","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":"Q1838829$BC244CD8-BFDF-4019-B6BA-0B82EDD3769A","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":"Q1838829$7A56DD84-2EB1-4235-8C90-28291A977560","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":"Q1838829$61553170-861E-4944-9186-542462E80EAD","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":"Q1838829$9DFB2FFE-BDD8-491A-A807-6844D3F0BCD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e16d1dc4052e71d6b4ce452bdd1e1e49e7dff8b","datavalue":{"value":{"entity-type":"item","numeric-id":4144192,"id":"Q4144192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1838829$92CA5771-96A0-46A6-B169-975EF9FE5D1A","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":"Q1838829$80A48EE8-9BDF-4B04-98ED-AE34F6572985","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":"Q1838829$699EE7C3-3457-46CC-971E-802ADC9B33E1","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":"Q1838829$657D5F87-83B3-484E-85C8-502486BA93EF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0e4565c5bd5e790d51a0a985d2cd7e145e14290f","datavalue":{"value":"https://doi.org/10.1016/0166-218x(83)90101-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1838829$D7A62A72-E03D-4F18-8420-CEB7BA5EEBB9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"214dd3be3df988351e706785d9b108363ea67c00","datavalue":{"value":"W2022137727","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1838829$FCEF530E-9188-4423-AB41-4E42E3465086","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the NP-hardness of edge-deletion and -contraction problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_NP-hardness_of_edge-deletion_and_-contraction_problems"}}}}}