Approximation Algorithms for Minimum-Time Broadcast

DOI10.1137/S0895480193245923MaRDI QIDQ4847364zbMATH OpenFDO

Authors Guy Kortsarz, David Peleg

Publication date 10 January 1996

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480193245923

zbMATH Keywords

NP-completeoptimal scheduleminimum broadcast timepolynomial approximation algorithmsbroadcast approximation algorithmsopen-path communication modeltelephone communication model

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1875435
• Constant approximation for broadcasting in k-cycle graph
• Polynomial-time algorithms for minimum-time broadcast in trees
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem

Cited in

(34)

• A linear algorithm for finding the k‐broadcast center of a tree
• Constant approximation for broadcasting in k-cycle graph
• scientific article; zbMATH DE number 1875435 (Why is no real title available?)
• Minimum-time multidrop broadcast
• scientific article; zbMATH DE number 4090796 (Why is no real title available?)
• Trade-offs between the size of advice and broadcasting time in trees
• \textsc{Telephone Broadcast} on graphs of treewidth two
• Polynomial-time algorithms for minimum-time broadcast in trees
• On the number of broadcast schemes in networks
• Finding broadcast 2-centers of a tree under the postal model
• Rumors across radio, wireless, telephone
• Improved approximation for broadcasting in k-path graphs
• A note on line broadcast in digraphs under the edge-disjoint paths mode
• Strong bounds and exact solutions to the minimum broadcast time problem
• Sublogarithmic approximation for telephone multicast
• Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem
• On the complexity of the shortest-path broadcast problem
• A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
• Approximating All-to-All Broadcast in Wireless Networks
• Degree- and time-constrained broadcast networks
• Broadcast Extensions with Optimal Communication and Round Complexity
• scientific article; zbMATH DE number 1670545 (Why is no real title available?)
• scientific article; zbMATH DE number 4141826 (Why is no real title available?)
• Parameterized Complexity of Broadcasting in Graphs
• Broadcasting and three list subtraction
• Approximation algorithms in graphs with known broadcast time of the base graph
• Broadcasting on cactus graphs
• A note to non-adaptive broadcasting
• Minimizing setup in broadcast-optimal two round MPC
• Broadcasting in weighted trees under the postal model
• Radio aggregation scheduling
• Tighter bounds on the minimum broadcast time
• On broadcasting in unicyclic graphs
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2

This page was built for publication: Approximation Algorithms for Minimum-Time Broadcast

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4847364)