Name
Abstract | ||
|---|---|---|
We study the problem of computing ad-hoc selective families: Given a collection F of subsets of [n] = {1, 2, . . ., n}, a selective family for F is a collection S of subsets of [n] such that for any F ? F there exists S ∈ S such that |F ∩ S| = 1. We first provide a polynomialtime algorithm that, for any instance F, returns a selective family of size O((1 + log(Δmax/Δmin)) ċ log |F|) where Δmax and Δmin denote the maximal and the minimal size of a subset in F, respectively. This result is applied to the problem of broadcasting in radio networks with known topology. We indeed develop a broadcasting protocol which completes any broadcast operation within O(DlogΔlog n/D) time-slots, where n, D and Δ denote the number of nodes, the maximal eccentricity, and the maximal in-degree of the network, respectively. Finally, we consider the combinatorial optimization problem of computing broadcasting protocols with minimal completion time and we prove some hardness results regarding the approximability of this problem. |
Year | Venue | Keywords |
|---|---|---|
2001 | RANDOM-APPROX | combinatorial optimization problem,ad-hoc selective family,broadcasting protocol,minimal completion time,computing ad-hoc selective families,maximal in-degree,selective family,instance f,maximal eccentricity,log n,collection f,col |
Field | DocType | Volume |
Broadcasting,Discrete mathematics,Combinatorics,Radio networks,Combinatorial optimization problem,Combinatorial optimization,Transmission protocol,Time complexity,Mathematics,Distributed computing | Conference | 2129 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-42470-9 | 15 |
PageRank | References | Authors |
0.90 | 13 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea E. F. Clementi | 1 | 1168 | 85.30 |
| Pierluigi Crescenzi | 2 | 1002 | 95.31 |
| Angelo Monti | 3 | 671 | 46.93 |
| Paolo Penna | 4 | 206 | 17.77 |
| Riccardo Silvestri | 5 | 1324 | 90.84 |