×

Broadcasting in conflict-aware multi-channel networks. (English) Zbl 1379.68012

Ghosh, Subir Kumar (ed.) et al., WALCOM: algorithms and computation. 7th international workshop, WALCOM 2013, Kharagpur, India, February 14–16, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36064-0/pbk). Lecture Notes in Computer Science 7748, 158-169 (2013).
Summary: The broadcasting problem asks for the fastest way of transmitting a message to all nodes of a communication network. We consider the problem in conflict-aware multi-channel networks. These networks can be modeled as undirected graphs in which each edge is labeled with a set of available channels to transmit data between its endpoints. Each node can send and receive data through any channel on its incident edges, with the restriction that it cannot successfully receive through a channel when multiple neighbors send data via that channel simultaneously.
We present efficient algorithms as well as hardness results for the broadcasting problem on various network topologies. We propose polynomial time algorithms for optimal broadcasting in grids, and also for trees when there is only one channel on each edge. Nevertheless, we show that the problem is NP-hard for trees in general, as well as for complete graphs. In addition, we consider balanced complete graphs and propose a policy for assigning channels to these graphs. This policy, together with its embedded broadcasting schemes, result in fault-tolerant networks which have optimal broadcasting time.
For the entire collection see [Zbl 1258.68010].

MSC:

68M10 Network design and communication in computer systems
68M15 Reliability, testing and fault tolerance of networks and computer systems
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI