Modelling simultaneous broadcasting by level-disjoint partitions

DOI10.1016/J.AMC.2017.12.018MaRDI QIDQ2279226zbMATH OpenOpenAlexFDO

Authors Petr Gregor, Riste Škrekovski, Vida Vukašinović

Publication date 12 December 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.01116

zbMATH Keywords

interconnection networkslevel-disjoint partitionsmultiple message broadcastingsimultaneous broadcasting

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Simultaneous broadcasting of multiple messages from the same source vertex in synchronous networks is considered under restrictions that each vertex receives at most one message in a unit time step, every received message can be sent out only in the next time step, no message is sent to already informed vertex. The number of outgoing messages in unrestricted, messages have unit length, and we assume full-duplex mode. In [9] we developed a concept of level-disjoint partitions to study simultaneous broadcasting under this model. In this work we consider the optimal number of level-disjoint partitions. We also provide a necessary condition in terms of eccentricity and girth on existence of $k$ $v$-rooted level-disjoint partitions of optimal height. In particular, we provide a structural characterization of graphs admitting two level-disjoint partitions with the same root.

Recommendations

• Broadcasting multiple messages in the 1-in port model in optimal time
• Rooted level-disjoint partitions of Cartesian products
• Time-optimal broadcasting of multiple messages in 1-in port model
• Multi-messages broadcasting in simultaneously send/receive communication networks
• Minimum multiple message broadcast graphs

Cites work

• A fast parallel algorithm for constructing independent spanning trees on parity cubes
• A survey of gossiping and broadcasting in communication networks
• All-to-all broadcast problem of some classes of graphs under the half duplex all-port model
• All-to-all broadcast problems on Cartesian product graphs
• Construction of optimal independent spanning trees on folded hypercubes
• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• Efficient construction of broadcast graphs
• Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
• Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults
• Independent spanning trees on even networks
• Methods and problems of communication in usual networks
• Minimum multiple message broadcast graphs
• Mutually independent Hamiltonian cycles of binary wrapped butterfly graphs
• Mutually independent hamiltonian paths in star networks
• On the mutually independent Hamiltonian cycles in faulty hypercubes
• Optimal multiple message broadcasting in telephone-like communication systems
• Rooted level-disjoint partitions of Cartesian products
• Time-optimal broadcasting of multiple messages in 1-in port model

Cited in

(4)

• Broadcasting multiple messages in the 1-in port model in optimal time
• Time-optimal broadcasting of multiple messages in 1-in port model
• Vertex-independent spanning trees in complete Josephus cubes
• Rooted level-disjoint partitions of Cartesian products

This page was built for publication: Modelling simultaneous broadcasting by level-disjoint partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279226)