{"entities":{"Q476891":{"pageid":478658,"ns":120,"title":"Item:Q476891","lastrevid":62159346,"modified":"2026-04-11T04:09:31Z","type":"item","id":"Q476891","labels":{"en":{"language":"en","value":"Inapproximability of dominating set on power law graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6375994"}},"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":"Q476891$06E18BAF-30C2-4DCB-AB28-28187F54F03A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8fc53bef9e46acc6f03b068ed676519ffd2dd305","datavalue":{"value":{"text":"Inapproximability of dominating set on power law graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q476891$F384C229-B777-48ED-B065-9E46EF3D9C9D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f6362a494f57203cffde83edad97477a9923164f","datavalue":{"value":"1305.05174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476891$526F91E0-2384-4019-8417-B7F847D2392F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f4431a4ac9a8929da479541f976dca47507ff2da","datavalue":{"value":{"entity-type":"item","numeric-id":385958,"id":"Q385958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$BBF1C072-2A3F-4019-BA6F-879A8AA182C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a84fe17c66f91d6ae80f1b13c4e0a7e224dd0ff2","datavalue":{"value":{"entity-type":"item","numeric-id":385959,"id":"Q385959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$FE577964-A912-4682-9F86-0E0A7CD9CF22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"572a13162b6df712d7941005f95a34b361dad87b","datavalue":{"value":{"entity-type":"item","numeric-id":396628,"id":"Q396628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$27F16417-978A-41E3-A79D-A4387F2B549B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$5AA90972-9FC7-4F8E-8AED-4D8B20C5E7C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"73dfefec2f6ca5d698146ea0cb5593f631aa8cde","datavalue":{"value":{"time":"+2014-12-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q476891$55FD3B9A-89E6-4157-B343-C886FEEDA8EE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"28f2fa0a7c8e1b9a3ea1772edc720ad161556ff9","datavalue":{"value":"https://arxiv.org/abs/1212.3517","type":"string"},"datatype":"url"},"type":"statement","id":"Q476891$E1B2FAFF-98BC-42D4-889A-1DD1B04C3E91","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476891$47849492-80DD-4C85-A7BC-76AB2746E83C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476891$3D1F3AE3-2CA3-4126-933D-E7753488D274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476891$4D536836-889E-4A8F-A031-0F69C67B156E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476891$E854043D-D311-46D6-BE72-99E1FDB2D6B5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f74bda5e28b8053415a4f302acf1adc03c4746d","datavalue":{"value":"6375994","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476891$396CB1A7-0C9B-41CF-8237-A4A8C63B892A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q476891$EECA1E4E-236E-41B9-AF96-7BABCB22194F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51f95efbd0445c23f397467c5e509da28dd67bbc","datavalue":{"value":"inapproximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q476891$7DAFF44F-C87A-40E9-BB15-2E3D514E21EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8390f398be5f32ca1623df59cf82a21fff53e80","datavalue":{"value":"power law graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q476891$315B1233-9506-48C5-8E35-5C1EFA11C242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q476891$6FA2119C-DB78-494D-85A7-3C5553D2B3DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q476891$7D4F50F0-8BA7-496F-95F9-F2DF6780EBBB","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":"Q476891$02EBDCBF-5502-4463-9ADB-84696DA4A2BA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1312eeb4d5f8d5242cc2f973869172ac76a56802","datavalue":{"value":"W2964161862","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476891$56D02E18-67FC-4485-A36C-33C98951D7A9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae46a3d079ac4fbf58b32c0239c12d18643f733c","datavalue":{"value":{"entity-type":"item","numeric-id":3191983,"id":"Q3191983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$77135DAD-DACB-4563-9379-DFF0B5FB4B32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d9808d3849625309eb8817cf22443150b62e4d5","datavalue":{"value":{"entity-type":"item","numeric-id":2729376,"id":"Q2729376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$44AD4F46-7F99-494A-BB67-4E193DA9002A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"349d7ef85d935a77ed55af1929cb6c2c4498301d","datavalue":{"value":{"entity-type":"item","numeric-id":3101363,"id":"Q3101363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$2CDCC7AC-2FE1-46C6-B1C1-967BF4C739E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85780c221de18da5da64e11400702277032a50cd","datavalue":{"value":{"entity-type":"item","numeric-id":1827728,"id":"Q1827728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$E22551DD-6603-42D1-B7C5-A961DCB5E832","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e255c436f4d8bfbdf7a5f27d6de3d2c926d2873","datavalue":{"value":{"entity-type":"item","numeric-id":5501331,"id":"Q5501331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$12627F9A-0ABB-4C07-946C-859EDBB01B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783f5b77f65178466163307ca17329fb72140e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$23C6AB21-4701-4B9D-BF1A-647EEACE1306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"927d76089cf1add6169f72f31b291f239d81e7ab","datavalue":{"value":{"entity-type":"item","numeric-id":2481967,"id":"Q2481967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$95E420B7-5E40-4C8B-B469-1CE4D68484B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ca5d14fccde023a59b39b6290c1056765545e22","datavalue":{"value":{"entity-type":"item","numeric-id":385960,"id":"Q385960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$AB44AAB5-9A99-4ED0-83C8-EB7268C08D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc7072c5fdf28dde940fb9d214f54b5a1227138","datavalue":{"value":{"entity-type":"item","numeric-id":1569419,"id":"Q1569419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$512D17C4-2374-4547-8064-A7D6613E1717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d5cfedfe66a3b5d774d6c8fbd31b828323bdab","datavalue":{"value":{"entity-type":"item","numeric-id":4527015,"id":"Q4527015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$4045C719-AC6F-4A2C-B741-0942BCDC2DF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fded291daf36307f43baeb3ebb14abe510418991","datavalue":{"value":{"entity-type":"item","numeric-id":443723,"id":"Q443723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476891$A60684A0-5D16-4AF5-A64E-C8AD12B61D72","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d08c916e56f5ca98399adc3cf4a408c844c21f25","datavalue":{"value":"10.1016/J.TCS.2014.10.021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476891$4C3B6279-FBCD-4E70-ACE2-4B063D389C7F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3eb7ba06fff69816cf954dc519d5eb459cd0f465","datavalue":{"value":{"entity-type":"item","numeric-id":3066157,"id":"Q3066157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"852315e37ad5506fb5d1c5fe3f59f9cf93b4b3a7","datavalue":{"value":{"amount":"+0.8601535558700562","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":"Q476891$DFC86AD6-9391-4D04-8D24-FD9113FFAA94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4f9ba719972811696b4265b607ee176b8bf840c","datavalue":{"value":{"entity-type":"item","numeric-id":443723,"id":"Q443723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"429a6a29b177b46ac96f9fa0410fcbe6364223a8","datavalue":{"value":{"amount":"+0.8374032378196716","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":"Q476891$985A947F-40DF-4027-A4CE-F2CD68251885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66efa05ab24cb58ac72cb32c3eb16325dbc91321","datavalue":{"value":{"entity-type":"item","numeric-id":958303,"id":"Q958303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e86b1d7769b630f90dce4e67c7762bbf09583253","datavalue":{"value":{"amount":"+0.8302656412124634","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":"Q476891$F07B196E-589A-4C2D-A97C-4F7FB8AF3464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa3a3d61919ec2ca9c97adedebcedce94cd9f0e8","datavalue":{"value":{"entity-type":"item","numeric-id":5464578,"id":"Q5464578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50167c5e97ea53e7bce682052a0e0a7c50bba83c","datavalue":{"value":{"amount":"+0.8241527676582336","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":"Q476891$50084B2B-A365-4036-BBE6-DAA1719C5AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89c7e1e265f85728311af313fa188324bee318e3","datavalue":{"value":{"entity-type":"item","numeric-id":2913785,"id":"Q2913785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c63b819bedf0f03c8c978d26b095ca9c00c09460","datavalue":{"value":{"amount":"+0.8151079416275024","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":"Q476891$9AA0C3FA-24B5-4D44-AC8E-1DBBB97A5AC1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Inapproximability of dominating set on power law graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Inapproximability_of_dominating_set_on_power_law_graphs"}}}}}