MINIMUM BROADCAST TIME IS NP-COMPLETE FOR 3-REGULAR PLANAR GRAPHS ANDDEADLINE 2

Authors
MIDDENDORF M
Citation
M. Middendorf, MINIMUM BROADCAST TIME IS NP-COMPLETE FOR 3-REGULAR PLANAR GRAPHS ANDDEADLINE 2, Information processing letters, 46(6), 1993, pp. 281-287
Citations number
6
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
46
Issue
6
Year of publication
1993
Pages
281 - 287
Database
ISI
SICI code
0020-0190(1993)46:6<281:MBTINF>2.0.ZU;2-S
Abstract
The Minimum Broadcast Time (MBT) problem is whether a piece of informa tion can be disseminated in a graph from a set of source nodes to all other nodes of the graph in at most k time steps. It is assumed that i n one time step each node that contains the information can broadcast it to at most one of its neighbours. We show that MBT is NP-complete f or 3-regular planar graphs and a constant deadline k greater-than-or-e qual-to 2.