Time-optimal broadcasting of multiple messages in 1-in port model

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10333120" target="_blank" >RIV/00216208:11320/16:10333120 - isvavai.cz</a>
Result on the web
<a href="http://link.springer.com/chapter/10.1007%2F978-3-319-48749-6_11" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-319-48749-6_11</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-48749-6_11" target="_blank" >10.1007/978-3-319-48749-6_11</a>

Result language
angličtina
Original language name
Time-optimal broadcasting of multiple messages in 1-in port model
Original language description
In the 1-in port model, every vertex of a synchronous network can receive each time unit at most one message. We consider simultaneous broadcasting of multiple messages from the same source in such networks with an additional restriction that every received message can be sent out to neighbors only in the next time unit and never to already informed vertex. We use a general concept of level-disjoint partitions developed for this scenario. Here we introduce a subgraph extension technique for efficient spreading information within this concept. Surprisingly, this approach with so called biwheels leads to simultaneous broadcasting of optimal number of messages on a wide class of graphs in optimal time. In particular, we provide tight results for bipartite tori, meshes, hypercubes. Several problems and conjectures are proposed.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA14-10799S" target="_blank" >GA14-10799S: Hybercubic, graph and hypergraph structures</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)