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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-10799S" target="_blank" >GA14-10799S: Hyperkrychlové, grafové a hypergrafové struktury</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

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

Název statě ve sborníku

Lecture Notes in Computer Science

ISBN

978-3-319-48748-9

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

15

Strana od-do

144-158

Název nakladatele

Springer International Publishing

Místo vydání

Neuveden

Místo konání akce

Hong Kong

Datum konání akce

16. 12. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—