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

Petr Gregor (), Riste Škrekovski () and Vida Vukašinović ()
Additional contact information
Petr Gregor: Charles University
Riste Škrekovski: University of Ljubljana
Vida Vukašinović: Jožef Stefan Institute

Journal of Combinatorial Optimization, 2018, vol. 36, issue 4, No 12, 1333-1355

Abstract: Abstract 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, Knödel graphs, circulant graphs. We also propose several open problems and conjectures.

Keywords: Simultaneous broadcasting; Multiple message broadcasting; Level-disjoint partitions; Torus; Mesh; Hypercube; Knödel graph; Circulant graph (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0274-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:4:d:10.1007_s10878-018-0274-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0274-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().