A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem

DOI10.1137/S0097539704440740zbMath1095.68130MaRDI QIDQ5470708

Michael Elkin, Guy Kortsarz

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

graphapproximationmulticastdirected

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (8)

The complexity of finding a broadcast center ⋮ A generalized broadcasting schema for the mesh structures ⋮ On the complexity of the shortest-path broadcast problem ⋮ Messy broadcasting - decentralized broadcast schemes with limited knowledge ⋮ Radio aggregation scheduling ⋮ The worst case behavior of randomized gossip protocols ⋮ Broadcasting on cactus graphs ⋮ Broadcasting on networks of workstations

This page was built for publication: A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem