𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A randomized algorithm for gossiping in radio networks

✍ Scribed by Marek Chrobak; Leszek Ga̧sieniec; Wojciech Rytter

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
100 KB
Volume
43
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We present an O(n log^4^n)‐time randomized algorithm for gossiping in radio networks with unknown topology. This is the first algorithm for gossiping in this model whose running time is only a polylogarithmic factor away from the optimum. The fastest previously known (deterministic) algorithm for this problem works in time O(n^3/2^log^2^n). © 2004 Wiley Periodicals, Inc.

📜 SIMILAR VOLUMES

An expanded maximum neural network algor
An expanded maximum neural network algorithm for a channel assignment problem in cellular radio networks
✍ Katsuyoshi Ikenaga; Yoichi Takenaka; Nobuo Funabiki 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 2 views

In this paper, we propose a neural network algorithm that uses the expanded maximum neuron model to solve the channel assignment problem of cellular radio networks, which is an NP-complete combinatorial optimization problem. The channel assignment problem demands minimizing the total interference be

Parallel Island-Based Genetic Algorithm
Parallel Island-Based Genetic Algorithm for Radio Network Design
✍ Patrice Calégari; Frédéric Guidec; Pierre Kuonen; Daniel Kobler 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 218 KB

This paper uses a realistic combinatorial optimization problem as an example to show how a genetic algorithm can be parallelized in an efficient way. The problem considered is the selection of the best set of transmitter locations in order to cover a given geographical region at optimal cost. It is