The minimum broadcast time problem for several processor networks

DOI10.1016/0304-3975(94)00230-GzbMath0873.68009OpenAlexW1992175439MaRDI QIDQ672455

Klaus Jansen, Haiko Müller

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00230-g

zbMATH Keywords

NP-completenessbroadcasting

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (8)

The multiple originator broadcasting problem in graphs ⋮ Polynomial algorithms for open plane graph and subgraph isomorphisms ⋮ Broadcasting in split graphs ⋮ A matheuristic approach for the minimum broadcast time problem using a biased random‐key genetic algorithm ⋮ Approximation algorithms in graphs with known broadcast time of the base graph ⋮ Tighter bounds on the minimum broadcast time ⋮ Finding a minimum medial axis of a discrete shape is NP-hard ⋮ A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• A simplified NP-complete satisfiability problem
• Rectilinear planar layouts and bipolar orientations of planar graphs
• A survey of gossiping and broadcasting in communication networks
• Broadcast Networks of Bounded Degree
• Minimal broadcast networks
• Information Dissemination in Trees
• Planar Formulae and Their Uses
• Broadcasting in Trees with Multiple Originators
• Broadcasting in Bounded Degree Graphs
• Gossiping in Minimal Time
• Tight Bounds on Mimimum Broadcast Networks

This page was built for publication: The minimum broadcast time problem for several processor networks