Approximation Algorithms for Minimum-Time Broadcast
From MaRDI portal
Publication:4847364
DOI10.1137/S0895480193245923zbMath0829.05056MaRDI QIDQ4847364
Publication date: 10 January 1996
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
NP-completeoptimal scheduleminimum broadcast timepolynomial approximation algorithmsbroadcast approximation algorithmsopen-path communication modeltelephone communication model
Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (15)
Degree- and time-constrained broadcast networks ⋮ On the number of broadcast schemes in networks ⋮ Approximation algorithms in graphs with known broadcast time of the base graph ⋮ On the complexity of the shortest-path broadcast problem ⋮ Tighter bounds on the minimum broadcast time ⋮ Radio aggregation scheduling ⋮ A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem ⋮ Broadcasting on cactus graphs ⋮ A note on line broadcast in digraphs under the edge-disjoint paths mode ⋮ Trade-offs between the size of advice and broadcasting time in trees ⋮ Sublogarithmic approximation for telephone multicast ⋮ A linear algorithm for finding the k‐broadcast center of a tree ⋮ Broadcasting in weighted trees under the postal model ⋮ On broadcasting in unicyclic graphs ⋮ Bicriteria Network Design Problems
This page was built for publication: Approximation Algorithms for Minimum-Time Broadcast
