Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
From MaRDI portal
Publication:685502
DOI10.1016/0020-0190(93)90066-IzbMath0777.68027OpenAlexW2091912668MaRDI QIDQ685502
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
Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)
Related Items (12)
Methods and problems of communication in usual networks ⋮ Degree- and time-constrained broadcast networks ⋮ Broadcasting a file in a communication network ⋮ The complexity of broadcasting in planar and decomposable graphs ⋮ Broadcasting in split graphs ⋮ Approximation algorithms in graphs with known broadcast time of the base graph ⋮ Tighter bounds on the minimum broadcast time ⋮ The minimum broadcast time problem for several processor networks ⋮ The complexity of broadcasting in planar and decomposable graphs ⋮ Rumor spreading with bounded in-degree ⋮ APX-hardness and approximation for the \(k\)-burning number problem ⋮ APX-hardness and approximation for the \(k\)-burning number problem
Cites Work
This page was built for publication: Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
