{"entities":{"Q5958835":{"pageid":8135637,"ns":120,"title":"Item:Q5958835","lastrevid":41618622,"modified":"2025-05-06T10:49:04Z","type":"item","id":"Q5958835","labels":{"en":{"language":"en","value":"Minimum connected dominating sets of random cubic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1716038"}},"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":"Q5958835$CCDDE6CE-8B85-48B0-8EB8-11DF4A86BBA6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ae4e35c2c598eef3d39159c3fdd67fb485fa8269","datavalue":{"value":{"text":"Minimum connected dominating sets of random cubic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958835$6CDE9582-33E7-4F18-BF54-53AC43CACDAB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"26a24ba7869de96b4bf9b29258c403912b2e8197","datavalue":{"value":"0986.05089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958835$348F3375-29F0-4367-B300-D2CE6C4BA331","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd1fe0a9e76938122d0c147e022b872272d0a9bb","datavalue":{"value":{"entity-type":"item","numeric-id":876694,"id":"Q876694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958835$87FA53E5-FC9C-4762-8255-2101271BCD5A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958835$9D101386-53B9-4C92-812D-F27E137FF4D1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"245de3561415d840eacdb8a4595bad612c89de00","datavalue":{"value":{"time":"+2002-03-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958835$C54CEB9A-C3C7-46DD-B85C-46EFE63FB869","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bf39203ba1839fb65b5010a1114acdfa70b4f102","datavalue":{"value":"https://eudml.org/doc/121821","type":"string"},"datatype":"url"},"type":"statement","id":"Q5958835$F6B2C400-2664-49F6-BF38-B27F646E2269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"5936740da65e2445dbe9efdf35a50853921f260a","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i1r7.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q5958835$871FBB92-D38E-4932-8CC3-14CC2F440CDC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"25d8526fe31490b2d1777666b12205279efddbcc","datavalue":{"value":"Summary: We present a simple heuristic for finding a small connected dominating set of cubic graphs. The average-case performance of this heuristic, which is a randomised greedy algorithm, is analysed on random \\(n\\)-vertex cubic graphs using differential equations. In this way, we prove that the expected size of the connected dominating set returned by the algorithm is asymptotically almost surely less than \\(0.5854n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958835$2D289D8B-6BD3-4E59-BD0B-3608A5A5E947","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958835$0B909A12-A327-4896-8274-9100355CFF49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958835$F3F3C065-DF2F-4711-9A7C-C6D84B23ACC3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e734ec581dc8901d8a2122e1634e0cb3dfdee247","datavalue":{"value":"1716038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958835$441BB500-237D-46DF-AE4B-E35818570F53","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958835$687D45AE-39A1-40C4-864D-E3D6E1B8CD9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"663f171d615b457c913c22c14ba5bd660f645156","datavalue":{"value":"cubic graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958835$F833F147-761D-4E93-9252-AD97A377EE1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95808b553deada1622b3adfecfe79df17f39c3d0","datavalue":{"value":"connected dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958835$B3AB9A7A-714C-4C91-96F6-754F9826B38D","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":"Q5958835$DFEF75C8-95CE-452B-82C8-3B1376DF4787","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"b77d0774b7b6fb477ee5d90bbb6b7ae04813899a","datavalue":{"value":"bafkreicwjboul2s2xmb5phjhvxgm3l3ap56a4snsuxvsmq6yladmlep2ya","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958835$20AAD303-2053-415C-B1F4-1F8B95C37062","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3640e9b7ae9270f1f29904f1c46b96eb9305f453","datavalue":{"value":{"entity-type":"item","numeric-id":4803314,"id":"Q4803314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bafac61b39fc2080571ac272daaf6ed6fa1d4a0","datavalue":{"value":{"amount":"+0.960887","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":"Q5958835$A2A57AE9-4C1F-47A3-960B-8F3C98D75997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55b7b03849417d2a3d64ec2d7d0c6541a28ec163","datavalue":{"value":{"entity-type":"item","numeric-id":5272639,"id":"Q5272639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce984776162a54972f2ab4607c4ce7587732591f","datavalue":{"value":{"amount":"+0.95403725","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":"Q5958835$D3441697-1F77-4367-979A-D8F14B0C5ABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b7ff8e6ff6647d5adee39badf579877317234ea","datavalue":{"value":{"entity-type":"item","numeric-id":4851928,"id":"Q4851928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9752a4e919695fea782cae1c0ef59336b2f1343b","datavalue":{"value":{"amount":"+0.91702735","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":"Q5958835$2AF7528D-7A77-4CD1-9DCF-09FD7DA74384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f222d5cd8c7037f2a9ccc5c4dba7f0e1c1f857e","datavalue":{"value":{"entity-type":"item","numeric-id":3008015,"id":"Q3008015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf24af4f10e513a1a3814ecdb5ff39ad54eeee34","datavalue":{"value":{"amount":"+0.91441405","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":"Q5958835$82C714C4-882C-4F0D-955F-8CC29D992489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5a0f6ade71c04f32504530b21389ac110b7b305","datavalue":{"value":{"entity-type":"item","numeric-id":4027168,"id":"Q4027168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a1b3a60aee46c8022a2b8d84a2023b47423e0ae","datavalue":{"value":{"amount":"+0.90834576","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":"Q5958835$69668E07-EF02-46EB-9AB3-43F93458195E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6c288178242f367ce6fc3f11e8338d395cdaddd","datavalue":{"value":{"entity-type":"item","numeric-id":712285,"id":"Q712285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f590fd2c66042ffaceb623bc8052acb5f2ca1bb","datavalue":{"value":{"amount":"+0.8982191","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":"Q5958835$308891DD-9D45-4207-AE25-6975729B211B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f71c644bd42187adfb163fa45dba1dc91ab34b3","datavalue":{"value":{"entity-type":"item","numeric-id":2576833,"id":"Q2576833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8d31272045995cfe784ca74959a37a730efbc50","datavalue":{"value":{"amount":"+0.8973214","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":"Q5958835$2987CD0A-87C6-4376-B59E-313B5E4A2F5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32c22eab7837c13f5fcdb5635ce984e2db90d960","datavalue":{"value":{"entity-type":"item","numeric-id":4697813,"id":"Q4697813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1245db6469d2be759582c822e5e346b2b03b2ad","datavalue":{"value":{"amount":"+0.897262","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":"Q5958835$2CCFECDD-5DAA-4BD4-8160-B39F3F26F888","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958835","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958835"}}}}}