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

DOI10.1016/0020-0190(93)90066-IMaRDI QIDQ685502zbMATH OpenOpenAlexFDO

Authors 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) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)

Recommendations

• The minimum broadcast time problem for several processor networks
• The complexity of broadcasting in planar and decomposable graphs
• scientific article; zbMATH DE number 1191227
• Approximation Algorithms for Minimum-Time Broadcast
• scientific article; zbMATH DE number 1670545

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A survey of gossiping and broadcasting in communication networks
• Information Dissemination in Trees
• Planar 3DM is NP-complete

Cited in

(26)

• The minimum broadcast time problem for several processor networks
• Broadcast graph is NP-complete
• \textsc{Telephone Broadcast} on graphs of treewidth two
• Broadcasting in stars of cliques
• 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
• Broadcast schemes of hypercubes
• Methods and problems of communication in usual networks
• Degree- and time-constrained broadcast networks
• Bounds on broadcast time in well-connected graphs
• scientific article; zbMATH DE number 1670545 (Why is no real title available?)
• APX-hardness and approximation for the \(k\)-burning number problem
• scientific article; zbMATH DE number 4141826 (Why is no real title available?)
• A linear-time optimal broadcasting algorithm in stars of cliques
• 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
• Parameterized Complexity of Broadcasting in Graphs
• Broadcasting and three list subtraction
• Broadcasting two messages in wheel 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)