{"entities":{"Q328713":{"pageid":330480,"ns":120,"title":"Item:Q328713","lastrevid":61001613,"modified":"2026-04-10T20:31:59Z","type":"item","id":"Q328713","labels":{"en":{"language":"en","value":"A complexity dichotomy and a new boundary class for the dominating set problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6641536"}},"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":"Q328713$36C640BE-A8BC-4240-BE87-1C4D8C697019","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c11fb3493c2083135cc1ec3f8746f0bd08994574","datavalue":{"value":{"text":"A complexity dichotomy and a new boundary class for the dominating set problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q328713$1D81736A-1C6F-4C4D-8EC2-7A4AE7FCF9A7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02a1ed3666988bf2a812a431cd96cd7dd88c6912","datavalue":{"value":"1354.90111","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q328713$3EA81625-43DA-4498-B265-2D1C83AAB145","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dcf8815e3b257674fa147da7a4e7c92c91c0b3e3","datavalue":{"value":{"entity-type":"item","numeric-id":185429,"id":"Q185429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$F1BD341D-3DDB-48FF-9B18-2F5ACCA31F60","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5702c77775a0294f70ce79fb40b36e4014bf6c55","datavalue":{"value":{"time":"+2016-10-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q328713$F46BDB78-2A93-4FA2-BFA5-7DC8398B0AF0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q328713$E7FCAD91-0496-49FB-B337-E760C02DEE5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q328713$08B5B917-99D2-4519-B1A6-74F4762DAFA0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"afcddb2435923aa2ba3b7da4b80bf26ceb7d5bd1","datavalue":{"value":"6641536","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q328713$9D52200E-1F4E-4E33-9FAD-235FF0FCAD5B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q328713$AA5B1854-435B-4775-889F-F51891786EC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q328713$74B2FF98-DE4C-431A-80B4-3145B56E343D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q328713$4C32384A-17CB-422C-9570-C3B54AEB483C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca6fcd59c66c40becda2288cda347adddcad5952","datavalue":{"value":"boundary class","type":"string"},"datatype":"string"},"type":"statement","id":"Q328713$5BF788FA-C14D-4B0C-87E7-CC6811011A17","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"31fa63c410743cfcc0d3d0fbbea5c808c23ab314","datavalue":{"value":{"entity-type":"item","numeric-id":1669582,"id":"Q1669582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$1CA47BAF-9633-405B-8B75-C81B23DFDDEE","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":"Q328713$5D3AD647-1936-4464-BD75-E82E6DF7C1A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"58d5a66506020e746c7ca45ba19801db8ffa6107","datavalue":{"value":"https://doi.org/10.1007/s10878-015-9872-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q328713$DF796E3B-3BF1-4FCC-A860-CF9AF05EDECE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b5e575342f99ec29ccfa87bec55f49169c3ea59b","datavalue":{"value":"W2047820500","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q328713$C9BE8463-FA0C-4790-95E5-B979FACB308D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"75cdb01f77cdad8174605336df6c81bbf47a42ef","datavalue":{"value":{"entity-type":"item","numeric-id":2942401,"id":"Q2942401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$262B334B-2F5B-49D0-87B9-E028C8BD83C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f56ad8af090eb02ae2bb07cb67e49a92aff1e456","datavalue":{"value":{"entity-type":"item","numeric-id":892049,"id":"Q892049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$63BC5631-9697-4712-B384-7973DF21D204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9bd8d13f5903b70417fe46e0f72c2a38d0f1aaa","datavalue":{"value":{"entity-type":"item","numeric-id":4936659,"id":"Q4936659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$2FA87FF2-C5A1-49E2-B74F-0DF6155EF943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70d214b2a81885d9130e0965474e9cc21570b9de","datavalue":{"value":{"entity-type":"item","numeric-id":1414579,"id":"Q1414579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$3C807B18-1887-4DAE-AFED-CFA59BD5C67F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"690db07db906cd7dd025238f998539e2c0e1a264","datavalue":{"value":{"entity-type":"item","numeric-id":2465640,"id":"Q2465640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$3C086986-D9AA-4B00-A6A2-94A4C3888089","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e75c98186527a54192f15d2e27d0739e388071bd","datavalue":{"value":{"entity-type":"item","numeric-id":1877644,"id":"Q1877644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$DD75CE0A-49B5-412E-8A01-E66FA42D77CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b69b5b03a7ed1f39c895674d8c97ff4c5a0355f","datavalue":{"value":{"entity-type":"item","numeric-id":1176051,"id":"Q1176051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$9C5963A4-0D3F-4B7C-8AF3-0D0B672E345C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a45e13eb981a91bb81dd4b337f3fb700a1a77047","datavalue":{"value":{"entity-type":"item","numeric-id":794174,"id":"Q794174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$B66158E6-07FB-4D57-B335-C007FDECC60F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffa330222cc9e7c22a38a1d866db60d6f102fb7d","datavalue":{"value":{"entity-type":"item","numeric-id":814931,"id":"Q814931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$AF9915CE-7C50-440A-B007-D92EF6AC85C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97d79f2a19c91cd2ba4fa37712ddbf5dc04117a2","datavalue":{"value":{"entity-type":"item","numeric-id":764301,"id":"Q764301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$FD6D763D-D268-4AFA-A6FD-BAD7457CE2F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f380170dd9de5e69fb40eb46470ac085e19dc87a","datavalue":{"value":{"entity-type":"item","numeric-id":1174134,"id":"Q1174134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$5FFD9FC3-438B-4793-806B-472436146404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8fe56184955dbba620e4cb94dc309dfe37fcc19","datavalue":{"value":{"entity-type":"item","numeric-id":1974445,"id":"Q1974445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$4FA0C241-9CBC-41ED-A20A-E2DE3DF2192D","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":"Q328713$1F78CA2F-E169-470E-8699-9E9872DEA551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf6aae63c2b0c3739457d3119180fcd7df439974","datavalue":{"value":{"entity-type":"item","numeric-id":2636800,"id":"Q2636800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$84E5919E-3948-41DA-939E-BC94B1AA26BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e544681d1cccccf6a64f441d01b39904ae77095","datavalue":{"value":{"entity-type":"item","numeric-id":476308,"id":"Q476308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$CCBBC982-695B-4F67-9B35-95EF4C54EC81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7cf1cd878f46b9eeec5571ec20db3733fdf6b35","datavalue":{"value":{"entity-type":"item","numeric-id":1759872,"id":"Q1759872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$7F436701-A64C-4B5F-B90C-B9F68E658CF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6093fccf9d4dcf6f19dbafab6da0ece506415977","datavalue":{"value":{"entity-type":"item","numeric-id":3512606,"id":"Q3512606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$C01B2871-5349-4CF2-BDAD-66320FC275F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0806d578ec0c9d408994a5d0fc6d73b047705ebb","datavalue":{"value":{"entity-type":"item","numeric-id":4284972,"id":"Q4284972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$F0C7722B-049D-4859-9275-211A421328B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20ecdad41b5a7ad19af25d12395ebbff6dd994fd","datavalue":{"value":{"entity-type":"item","numeric-id":4448764,"id":"Q4448764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$01851297-8487-48B7-89B5-04F3AEA527D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bba93e1dc8cd8b64e0a3d51c288ab8d2942cca2e","datavalue":{"value":{"entity-type":"item","numeric-id":1962038,"id":"Q1962038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$4026D077-B5C2-41C5-AAE7-CED7BA8B19B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16cebb6b763969813ed9a495130a9f4e8d6efc62","datavalue":{"value":{"entity-type":"item","numeric-id":5200492,"id":"Q5200492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$3B5EFD93-E370-4987-BB87-906C9C30EDA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8807a77b16516cbd9e09421a89f1b5dfabfc8c7f","datavalue":{"value":{"entity-type":"item","numeric-id":5384003,"id":"Q5384003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$508A8557-8895-4834-AAAE-54F3EF2688A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aeea9c759438b4c0998879473dd96339053db2a4","datavalue":{"value":{"entity-type":"item","numeric-id":344868,"id":"Q344868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$1EEBA094-45A1-4548-B69C-94E845F547CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4278372d18270a2b00c0bb0fc547a55571bc535","datavalue":{"value":{"entity-type":"item","numeric-id":1765375,"id":"Q1765375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$B1CBC6C2-FDA9-4AFA-9A12-2A687F939E45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55952e378589454474128d8823a63680494eab6c","datavalue":{"value":{"entity-type":"item","numeric-id":2352049,"id":"Q2352049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$AFF32D69-564E-4D5C-BF99-37936A86A639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2cf87612e32344d86c82c7b3251b71bc3c7de80","datavalue":{"value":{"entity-type":"item","numeric-id":5264719,"id":"Q5264719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$F333B250-B5EE-43A6-9DEE-0033DF900054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e7032db704a3c4fcea69481a5580e82a7d02eda","datavalue":{"value":{"entity-type":"item","numeric-id":3903038,"id":"Q3903038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$19BC9023-39AD-48CE-BF8D-FFF1BAC0AF14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59f9a0b7570b7497c08adcc2b4a04cf8eba8ce94","datavalue":{"value":{"entity-type":"item","numeric-id":4405639,"id":"Q4405639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q328713$97DA222F-1617-496D-838F-363DD4109039","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f586c29d9da555968004afaaec077c402f48f858","datavalue":{"value":"10.1007/S10878-015-9872-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q328713$8C1B8D14-7DFC-432C-82EF-E4018B020FB5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"394217e50086d9b4f2386e97f677d0f163c64f66","datavalue":{"value":{"entity-type":"item","numeric-id":6054225,"id":"Q6054225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8588c51c8780e07f88a5d61d458b6a42b1131b1b","datavalue":{"value":{"amount":"+0.9213887453079224","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":"Q328713$5D21AD87-3CCA-422F-A2FB-C85967E2D2B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"606c5f452f172c83574136e434005946268e7e0d","datavalue":{"value":{"entity-type":"item","numeric-id":1877644,"id":"Q1877644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56b0cc1d0ddaf8e7edc68fc7acb042ffcbc51677","datavalue":{"value":{"amount":"+0.8854832649230957","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":"Q328713$880D1345-B68F-4F49-98FF-54C5A9B3F61A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4227f560ed618c495ceaeee70c366818991fcce","datavalue":{"value":{"entity-type":"item","numeric-id":722525,"id":"Q722525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5efc6f2ac07c5d30da06436e68e953a8c478d85a","datavalue":{"value":{"amount":"+0.8352519273757935","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":"Q328713$3F68D1B3-EF89-4C48-813C-203CC535DF3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c36ecc21e4c7745bdd96fab270a9c880272270e","datavalue":{"value":{"entity-type":"item","numeric-id":2819507,"id":"Q2819507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"625fd450643eec31632cb7812cd996505193ed46","datavalue":{"value":{"amount":"+0.8095078468322754","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":"Q328713$886E3FF7-E8C1-4F89-BA5F-7FAA5179641F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d83001658a726947102b6091f30af9fe3be62455","datavalue":{"value":{"entity-type":"item","numeric-id":5492624,"id":"Q5492624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc3d6f4b4a9b1609d37da85a78247331db4cbdf6","datavalue":{"value":{"amount":"+0.8033191561698914","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":"Q328713$8C622878-3296-4C93-8B3D-ADE6BFD1AD03","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A complexity dichotomy and a new boundary class for the dominating set problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_complexity_dichotomy_and_a_new_boundary_class_for_the_dominating_set_problem"}}}}}