{"entities":{"Q1382273":{"pageid":1393013,"ns":120,"title":"Item:Q1382273","lastrevid":67304661,"modified":"2026-04-12T16:43:35Z","type":"item","id":"Q1382273","labels":{"en":{"language":"en","value":"Broadcast and gossip in line-communication mode"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1133168"}},"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":"Q1382273$7EDBE309-65CC-4D34-9558-B8A377E7EB1C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8c9a31b9dfad89a7067fbdb20a942d022ea937f7","datavalue":{"value":{"text":"Broadcast and gossip in line-communication mode","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1382273$2F078873-35EF-452A-910E-5C3AA5D5CA64","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a749019206469e4178328bd58e9f8b8893d66c6a","datavalue":{"value":"0898.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382273$1C854E25-F043-4C45-A11F-50E908C6D2E3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"217d5eabd88111bb8011ce4886b72f7c344476b9","datavalue":{"value":"10.1016/S0166-218X(97)00054-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382273$CF29EB50-6A5E-4389-9562-3159A195A21E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382273$11F12A9E-A090-4A62-AA07-3F214E86B11D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"aeab5ec812a0ca5fb5a693de9fb212e9ec6262da","datavalue":{"value":{"time":"+1998-11-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1382273$B6757A78-F747-41EA-96F4-AEBFF294295F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1382273$DFD3D28C-D16C-4D36-A650-C8FF939AB1B0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ecddc5b9de9a2adbb3688fc0d14a9e4aefe43108","datavalue":{"value":"In a line-communication network, two nodes can communicate directly via a path in a single time step and different pairs of nodes can do so provided edge-disjoint paths are used. In the broadcast problem one node has a piece of information which is to be transmitted to all nodes; in the gossip problem each node has a distinct piece of information and all such pieces are to be transmitted to all nodes. The paper gives a simple proof of Farley's result that the broadcast time is \\(\\lceil \\log_2 n\\rceil\\) steps in a connected network with \\(n\\) nodes. For the gossip problem upper and lower bounds are given for the gossip time for connected graphs and for trees. Gossip algorithms are constructed for trees and are shown to be optimal or asymptotically optimal. Also trees are constructed in which gossip is possible in \\(\\lceil \\log_2n \\rceil\\) steps.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382273$99C88CA6-6CDB-46F2-A64C-DF43BC1E79AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382273$B88BEF04-9542-4EBE-BF13-B1CEC1FD27E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382273$07AA1E77-1B78-427B-B3DA-1BADC06ECB37","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"02c0bba4457411ab3aed7fbb260e47bded847da2","datavalue":{"value":"1133168","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382273$813058EF-C657-424E-B451-CE62CB3B1493","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8b90c87a2970b98a4546ceba68f00c53ea9209f","datavalue":{"value":"line-communication network","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382273$4078D8B7-0438-452A-BA69-E9923FFD24CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94b9b01014e0a505d4c4daaf4da08005e737fa2e","datavalue":{"value":"broadcast","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382273$59D5CDC2-26A1-49B7-B98F-91119FB41BCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6387dfc6f5cc582c466aa036bd17ea632c1b034","datavalue":{"value":"gossip","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382273$4325F718-26FA-4BC3-A8BA-B7EE2FF17C84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382273$05541C72-60E8-430B-8A96-DFE19179EC40","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec5ea9e815f621f9dc5be85af1bce3e9309e4c79","datavalue":{"value":{"entity-type":"item","numeric-id":186177,"id":"Q186177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382273$EB7C64DE-FD3A-44BC-83C5-F446A5A083D9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fc9a9343f144968eeb3ee891e737abff43a13ff0","datavalue":{"value":{"entity-type":"item","numeric-id":913778,"id":"Q913778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382273$0982702F-2A9A-4D4E-8DC6-AB7FBAA52628","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":"Q1382273$8FCA166D-96E8-475E-90BA-6BDA3584E950","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382273$50CCDBE4-5647-481B-8080-42BE4B5D8092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf84d099c69fee93359273af853e68a5a619084b","datavalue":{"value":{"entity-type":"item","numeric-id":3870643,"id":"Q3870643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382273$A8332D50-0ADC-4305-92BA-D9FE31F5FDDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45ebac093ca51e69a9d57552dc1a79ce5e942b50","datavalue":{"value":{"entity-type":"item","numeric-id":1339884,"id":"Q1339884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382273$2534EB1F-3A6B-4757-8BF9-2019172BCE45","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":"Q1382273$97B83526-53DE-49C2-A5C5-723F412B4726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a90750fdd11efdb1ce353c39558e2bb523da9a9e","datavalue":{"value":{"entity-type":"item","numeric-id":5054763,"id":"Q5054763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382273$EE19BB3B-7C0B-4DEB-A321-1CAA769CD661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15fa88633e6d86e9fe2595731b3f46fd463c918f","datavalue":{"value":{"entity-type":"item","numeric-id":1392536,"id":"Q1392536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382273$1012C9D7-1286-4AA5-8000-08D5B34D05EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f66a493575bc3fe44a5f4fabbbe2b3aa939ef862","datavalue":{"value":{"entity-type":"item","numeric-id":1217126,"id":"Q1217126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382273$B666973B-EE9A-49D6-8F58-4E7D889561AA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c942670c3df98eb5bf63ed933cdeda89bc7d488","datavalue":{"value":{"entity-type":"item","numeric-id":5054763,"id":"Q5054763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edb953f9505ca0e9c5cdcb4935c03d0987bb5430","datavalue":{"value":{"amount":"+0.8751150369644165","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":"Q1382273$D4EF71FB-BEB0-4956-BF66-913FFD77474B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b97a78d2904469c68068b4341876046d6150cfa","datavalue":{"value":{"entity-type":"item","numeric-id":1357008,"id":"Q1357008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba27cd501b41937a23f4b909f43242320c4332cf","datavalue":{"value":{"amount":"+0.8724566102027893","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":"Q1382273$6511674C-58E6-4FB8-AE50-E123934B43A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e56b3fa9bb9edba67fd4d097c46385cee6b9988a","datavalue":{"value":{"entity-type":"item","numeric-id":3795460,"id":"Q3795460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4236cc928d210b3e96211a92bf5333905eaab64b","datavalue":{"value":{"amount":"+0.8703739643096924","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":"Q1382273$C84EDACB-6B44-43F3-8756-AF333AC256DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ead55ee91ee814522e373a879693ddcfa6e61368","datavalue":{"value":{"entity-type":"item","numeric-id":3990105,"id":"Q3990105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8f6a9c9c8459d76fabf5dc00753f103ecd6f62c","datavalue":{"value":{"amount":"+0.8651677370071411","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":"Q1382273$9A3A3A06-F1A5-4E8D-8267-92F841E11BDC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Broadcast and gossip in line-communication mode","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Broadcast_and_gossip_in_line-communication_mode"}}}}}