Broadcasting multiple messages in the 1-in port model in optimal time |
| |
Authors: | Petr Gregor Riste ?krekovski Vida Vuka?inovi? |
| |
Institution: | 1.Department of Theoretical Computer Science and Mathematical Logic,Charles University,Prague,Czech Republic;2.Department of Mathematics,University of Ljubljana,Ljubljana,Slovenia;3.Faculty of Information Studies,Novo mesto,Slovenia;4.FAMNIT, University of Primorska,Koper,Slovenia;5.Computer Systems Department,Jo?ef Stefan Institute,Ljubljana,Slovenia |
| |
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: | |
本文献已被 SpringerLink 等数据库收录! |
|