Broadcasting multiple messages in the 1-in port model in optimal time

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10384206" target="_blank" >RIV/00216208:11320/18:10384206 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s10878-018-0274-x" target="_blank" >https://doi.org/10.1007/s10878-018-0274-x</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10878-018-0274-x" target="_blank" >10.1007/s10878-018-0274-x</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Broadcasting multiple messages in the 1-in port model in optimal time

Popis výsledku v původním jazyce

In the 1-in port model, every vertex of a synchronous network can receive at most one message in each time unit. We consider simultaneous broadcasting of multiple messages from the same source or from distinct sources 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, Knodel graphs, circulant graphs. We also propose several open problems and conjectures.

Název v anglickém jazyce

Broadcasting multiple messages in the 1-in port model in optimal time

Popis výsledku anglicky

In the 1-in port model, every vertex of a synchronous network can receive at most one message in each time unit. We consider simultaneous broadcasting of multiple messages from the same source or from distinct sources 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, Knodel graphs, circulant graphs. We also propose several open problems and conjectures.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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í

2018

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 periodika

Journal of Combinatorial Optimization

ISSN

1382-6905

e-ISSN

—

Svazek periodika

36

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

23

Strana od-do

1333-1355

Kód UT WoS článku

000446588200012

EID výsledku v databázi Scopus

2-s2.0-85043383216