Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
DOI10.1016/0020-0190(93)90066-IzbMATH Open0777.68027OpenAlexW2091912668MaRDI QIDQ685502FDOQ685502
Publication date: 17 October 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(93)90066-i
Recommendations
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)
Cites Work
Cited In (19)
- The minimum broadcast time problem for several processor networks
- Improved approximation for broadcasting in k-path graphs
- Strong bounds and exact solutions to the minimum broadcast time problem
- APX-hardness and approximation for the \(k\)-burning number problem
- Methods and problems of communication in usual networks
- Degree- and time-constrained broadcast networks
- Rumor spreading with bounded in-degree
- APX-hardness and approximation for the \(k\)-burning number problem
- Title not available (Why is that?)
- A linear-time optimal broadcasting algorithm in stars of cliques
- Title not available (Why is that?)
- Broadcasting a file in a communication network
- The complexity of broadcasting in planar and decomposable graphs
- The complexity of broadcasting in planar and decomposable graphs
- Approximation Algorithms for Minimum-Time Broadcast
- Broadcasting in split graphs
- Approximation algorithms in graphs with known broadcast time of the base graph
- A note to non-adaptive broadcasting
- Tighter bounds on the minimum broadcast time
This page was built for publication: Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685502)
