{"entities":{"Q1183397":{"pageid":1194146,"ns":120,"title":"Item:Q1183397","lastrevid":66442653,"modified":"2026-04-12T10:06:14Z","type":"item","id":"Q1183397","labels":{"en":{"language":"en","value":"Analysis of a greedy heuristic for finding small dominating sets in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33265"}},"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":"Q1183397$9CA78BB1-3151-4B55-A09A-AB82AC08B463","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f3ad8257966c7864c8b0a2099807db87cab064f4","datavalue":{"value":{"text":"Analysis of a greedy heuristic for finding small dominating sets in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183397$F5963B8F-48FF-454E-BEE5-C3C76F0CABD0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6f2f268ec0f68cbb319bb2b4573237b33a13f7c9","datavalue":{"value":"0746.05061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183397$01D2AF55-6013-482A-AEF5-08B1CA8ED78C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2a78b0c0a301e561c088f428b43586ff6cfb73ea","datavalue":{"value":"10.1016/0020-0190(91)90021-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183397$865802CF-F876-4B7B-AF07-601B15B9E2F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4e56cc40be7b9f8f46b13b37f309de558132d5d5","datavalue":{"value":{"entity-type":"item","numeric-id":1183396,"id":"Q1183396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183397$F7A6D253-7EE2-4CA0-9EB6-AB154B71ADB1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183397$2596DEC6-7C53-4F63-9835-2591C80D3E92","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183397$52386A4C-B4F4-4B29-BABE-C5D7A044D536","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7aa6f79c62ec5c795d0875811aec14019aa5f161","datavalue":{"value":"Consider the problem of finding a minimum dominating set in an undirected graph. The author obtains an upper bound on the size of the dominating set returned by the greedy algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183397$FE213432-F995-47D3-828C-DA6DB74D418C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183397$15160FA7-0031-40FD-AF31-74A7E28ED2DB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3b39d086bd5e8743768e081b5391a74741e08d71","datavalue":{"value":"33265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183397$8D36A29F-4E2F-4C88-8D79-978A39FE1903","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffaab57211c42389ae103fdf09ef3b9e45eecbc8","datavalue":{"value":"dominating sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183397$8AAB85D7-5635-4798-AADC-297BBECB1C38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd0ec47f2d4dab7908c2ebbe2726174dab4de56e","datavalue":{"value":"greedy heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183397$E1007FE7-A071-4343-8EED-4F184F4A6821","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":"Q1183397$33507E91-9B67-4350-8377-4C7C0EC2762A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ed5771c594ebfec79d438ccb6cb6daf54574cf2d","datavalue":{"value":"https://doi.org/10.1016/0020-0190(91)90021-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1183397$96C1B0EF-E54C-4118-BCAC-377528B8CDEB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7d445d201e0a05ad3205fc7140589e0710b5ea77","datavalue":{"value":"W2151624738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183397$11446B43-B2B8-4B3A-A68A-096F6D624836","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a80eed9f379f185c9ca92aab1fa2ad3cc4463c9","datavalue":{"value":{"entity-type":"item","numeric-id":3887227,"id":"Q3887227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183397$46D5D4CD-7958-48E5-A23F-933B5281BABD","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":"Q1183397$DC65121C-C8EA-41BF-A9E3-7B2E68899441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00a9e252dcd967174efec124226bbf4f16c443d8","datavalue":{"value":{"entity-type":"item","numeric-id":3947140,"id":"Q3947140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183397$908248C9-489E-4700-905A-16BEC45EF2D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183397$FB7883C7-7A37-45B2-870E-8137DCC74537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a40cbd364246837cca1f46b9b232da08f2ebb898","datavalue":{"value":{"entity-type":"item","numeric-id":5509541,"id":"Q5509541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183397$6DCB8AB9-55E9-4240-A0EC-5F6F6C695C81","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee0076a2721af5b6988a8edac5cbf52b6ca3c728","datavalue":{"value":{"entity-type":"item","numeric-id":5704842,"id":"Q5704842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ab1c522c952bff0751d42a7c14192d30030919e","datavalue":{"value":{"amount":"+0.9039551","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183397$D0FCB610-621E-4C3C-A6BE-B4E0ED986783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0982f9f42f866edc634881c89276b21b943f4296","datavalue":{"value":{"entity-type":"item","numeric-id":2366651,"id":"Q2366651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"533419cc489324ce53ab060f703c3336c627ec74","datavalue":{"value":{"amount":"+0.90134484","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183397$0E978C23-F012-437C-8646-380C24EA500C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1dd239904eb0d0f961f7ad006b5520d2744b3839","datavalue":{"value":{"entity-type":"item","numeric-id":1600994,"id":"Q1600994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8988a0f4d2832fb93dc89cfa86eb3a9b8d7a2ce","datavalue":{"value":{"amount":"+0.90023273","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183397$7A626232-D73F-4B25-AAC4-29E3CEBFEEDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85f3c7c52b00c9cd0959295232133cc61d83ac6e","datavalue":{"value":{"entity-type":"item","numeric-id":6102924,"id":"Q6102924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f78832bb57b62c285d0b2fd6d10bd81684833db","datavalue":{"value":{"amount":"+0.8910209","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183397$45B0669E-9FA9-4536-B7C9-4232BA9B0C86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3dc5df7f5fe66565ffb7dd4495f929c05ec0b7e0","datavalue":{"value":{"entity-type":"item","numeric-id":5696912,"id":"Q5696912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"126d2a52355ff56aacedad4025f5bc4c049b39ad","datavalue":{"value":{"amount":"+0.88775563","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183397$6E82FC9D-673E-4A4E-A920-CECA3B02555F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0382e4a9690c1aae4c907540ae3520f7e641f13d","datavalue":{"value":{"entity-type":"item","numeric-id":706637,"id":"Q706637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"144bfab782992711d90e32cf7a40408dbd0eb9b6","datavalue":{"value":{"amount":"+0.8864388","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183397$ABA99382-9E25-4246-82D5-06347D3EFFDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b72789893e871b304ef202e13c6c252d7f46d87","datavalue":{"value":{"entity-type":"item","numeric-id":1417582,"id":"Q1417582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfcd52e50181bc4bf5f654d5219fab14a6c4c79b","datavalue":{"value":{"amount":"+0.8846015","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183397$0CE16EFE-FDE5-473A-BA27-94E6E9ACBB76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39dc799a99ac6a7338636414548dea18050edaa6","datavalue":{"value":{"entity-type":"item","numeric-id":5397695,"id":"Q5397695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77ea160f134de4871b50f178e59e84cf0744ed2d","datavalue":{"value":{"amount":"+0.8807785","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183397$4CA0BBC8-69C7-4299-8CC2-F4A7BFF71285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3e943cc1efc8766e5de3ea583d425c477aba22b","datavalue":{"value":{"entity-type":"item","numeric-id":3634205,"id":"Q3634205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ca016a44f522bf631129d10da6f8e335bcb6516","datavalue":{"value":{"amount":"+0.8805624","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183397$A5B3D3CA-673A-4661-B183-9D672DD67439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37fe5753158e44bf3f177f7abee1f45ff0cc94f0","datavalue":{"value":{"entity-type":"item","numeric-id":4437499,"id":"Q4437499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e19199a2ace85b738d5df06f0cb7a93393631213","datavalue":{"value":{"amount":"+0.874553","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183397$6465A3C0-52D2-4981-8DDA-024D8490518A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Analysis of a greedy heuristic for finding small dominating sets in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Analysis_of_a_greedy_heuristic_for_finding_small_dominating_sets_in_graphs"}}}}}