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

broadcast approximation algorithmsminimum broadcast timeNP-completeopen-path communication modeloptimal schedulepolynomial approximation algorithmstelephone communication model

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) 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

(36)

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

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)