Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2

DOI10.1016/0020-0190(93)90066-IzbMath0777.68027OpenAlexW2091912668MaRDI QIDQ685502

Martin Middendorf

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

zbMATH Keywords

combinatorial optimizationNP-completenessinformation dissemination

Mathematics Subject Classification ID

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

• Unnamed Item
• Planar 3DM is NP-complete
• A survey of gossiping and broadcasting in communication networks
• Information Dissemination in Trees

This page was built for publication: Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2