{"entities":{"Q685502":{"pageid":687351,"ns":120,"title":"Item:Q685502","lastrevid":47189050,"modified":"2025-12-31T23:10:58Z","type":"item","id":"Q685502","labels":{"en":{"language":"en","value":"Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417408"}},"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":"Q685502$ED11118C-2E1B-4280-A509-91F96E9CE773","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"01ac524b4c4e4cd6918124e3b6a2fd8bd45c0de9","datavalue":{"value":{"text":"Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685502$D157CCC7-2147-4928-A494-9233DAB56A0C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e68f044d9198e5b0557d5a9f10ede6aaf1debca6","datavalue":{"value":"0777.68027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685502$01767272-9E6F-470C-8981-4D37FE644B6F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7f808763a1f5d4fd81967b37221affd5e908eebb","datavalue":{"value":"10.1016/0020-0190(93)90066-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685502$E7EF4898-B95A-492D-AF51-6DECF619B46E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6c93b0e2919a1e814f26c792c784a99ad1c9581","datavalue":{"value":{"entity-type":"item","numeric-id":242846,"id":"Q242846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685502$830DD995-3B2C-4B6D-A822-E0AED672DB57","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":"Q685502$0D89627E-343A-4DC4-88D7-AE11FEFCDF1E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea9458ce3029a7f683c04e43e886fdc910ea299c","datavalue":{"value":{"time":"+1993-10-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685502$3F22D1A2-F9D5-4FD7-901A-D4912257E56F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c41153d050d7ff299123e84e849ffc1638c91f25","datavalue":{"value":"The MINIMUM BROADCAST TIME (MBT) problems is whether a piece of information can be disseminated in a graph from a set of source nodes at all other nodes of the graph in at most \\(k\\) time steps. It is assumed that in one time step each node that contains the information can broadcast it to at most one of its neighbours. We show that MBT is NP- complete for 3-regular planar graphs and a constant deadline \\(k\\geq 2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q685502$F7B0301C-9A44-4282-9669-1FF6A856426A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2499add345269c93c5ed1b650d8b90573cb6b1a8","datavalue":{"value":{"entity-type":"item","numeric-id":242846,"id":"Q242846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685502$2A752B4F-FEDF-476A-91E1-D4FCDE3B6F79","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca8c16691e9ec83d46a3995338b09d48ac9660ac","datavalue":{"value":"68M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685502$BC76927F-3F49-4A33-9E7D-78939D3E3673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685502$C69F61E9-16E9-4882-AED8-98A75FFD9615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685502$A29DE80D-1F35-436C-8BB7-28658DFC804B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685502$4D613EAA-2DFB-4C75-9719-FD0DB69A32DB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8d46c763ba1d023eaee64a4315ddb5466fa68fe3","datavalue":{"value":"417408","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685502$C7CF8B3F-1A6F-4F83-B097-7A9E83CE6AD8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q685502$1A79987E-F6DB-4A20-931D-6DC3A21E12A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a674fac19ec24da911619113c3d5c64edd285d74","datavalue":{"value":"information dissemination","type":"string"},"datatype":"string"},"type":"statement","id":"Q685502$2C0D3163-B640-4642-94F8-1D35864BCD75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q685502$ECD98D60-88C9-471B-819D-ACE3849C7D0C","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":"Q685502$42F77CFE-C9A5-4B9B-9340-4A8D9B19DCBF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6db8bab2b6b4db51137d491f1da9280274410f7a","datavalue":{"value":{"entity-type":"item","numeric-id":3745303,"id":"Q3745303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685502$7EB1523B-B92F-4EEA-AC35-47D4D3AE2FE6","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":"Q685502$D8235DC3-ABB4-46E7-8238-EBD0365EB8D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc47a36e1ac0c95d90450d3d1c8b7166990bef38","datavalue":{"value":{"entity-type":"item","numeric-id":3795460,"id":"Q3795460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685502$63FC8673-1158-41EB-A472-C21A6B1906F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b06dede5c993df3bade60414dfd78079ec2a10f3","datavalue":{"value":{"entity-type":"item","numeric-id":3922180,"id":"Q3922180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685502$4A4CA3B7-773F-45C8-B156-735A2D0FFFBD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"87991f9f13ad9644d33b26e7a4c5c754969564bc","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90066-i","type":"string"},"datatype":"url"},"type":"statement","id":"Q685502$49362F5A-C90C-4F41-825E-C3BE75805CF7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ff297dbcc751389643fad0e1bceb10e552af3084","datavalue":{"value":"W2091912668","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685502$593EBFB9-7B93-486C-8DFA-740C16EEEFC0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fd6e528571e66b3b8915358229ea50935d128ca","datavalue":{"value":{"entity-type":"item","numeric-id":672455,"id":"Q672455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec36ac51f1361e80f2adbc79abc91a1c5cd5313b","datavalue":{"value":{"amount":"+0.8557921648025513","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":"Q685502$6DC267E0-A730-4E50-826F-80C607C07315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07bd682f4737168dee9f830ed5200e1a89d4519b","datavalue":{"value":{"entity-type":"item","numeric-id":1392535,"id":"Q1392535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"874eaddd5aabb621ccef27807ea7172be164ea68","datavalue":{"value":{"amount":"+0.8303811550140381","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":"Q685502$C714381E-1B1D-4823-8891-62D60A6FBB86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"677cdbdc68f8bf3d89095ed6708260c24d6b0bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3842539,"id":"Q3842539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"874eaddd5aabb621ccef27807ea7172be164ea68","datavalue":{"value":{"amount":"+0.8303811550140381","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":"Q685502$5A594D07-475A-422A-8438-74CF7AC9E3D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa8679b1f2a381b3440687edcd7086c502a2cb68","datavalue":{"value":{"entity-type":"item","numeric-id":4847364,"id":"Q4847364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"116ec4762824ddc1b937559df1c3129a8a31493b","datavalue":{"value":{"amount":"+0.8269628882408142","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":"Q685502$604F171A-BE71-4F31-9046-DAC9724B5792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae0bf00be52f6429057fd9a75faede7ef5cc5d9a","datavalue":{"value":{"entity-type":"item","numeric-id":2753743,"id":"Q2753743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce4b3d9c26d592bc3307ad99b21789986fc698ff","datavalue":{"value":{"amount":"+0.8215010166168213","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":"Q685502$E25380F8-A280-4A9D-AAD3-7D080DBF2D2E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685502","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685502"}}}}}