×

The minimum broadcast time problem for several processor networks. (English) Zbl 0873.68009

Summary: Broadcasting is the information dissemination process in a communication network. A subset of processors \(V_{0}\subset V\) called originators knows an unique message which has to be transferred by calls between adjacent processors. Each call requires one time unit and each processor can participate in at most one call per time unit. The problem is to find a schedule such that the time needed to inform all processors is less than or equal to a deadline \(k\in {\mathbb{N}}\). We present NP-completeness results for this problem restricted to several communication networks (bipartite planar graphs, grid graphs, complete grid graphs, split graphs and chordal graphs) with constant deadline \(k=2\) or one originator \(V_0=v\).

MSC:

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

References:

[1] Bermond, J. C.; Hell, P.; Liestman, A. L.; Peters, J. G., Broadcasting in bounded degree graphs, SIAM J. Discrete Math., 5, 10-24 (1992) · Zbl 0753.68007
[2] Bermond, J. C.; Peyrat, C., Broadcasting in de Bruijn networks, (Proc. 19. S-E Conf. on Combinatorics, Graph Theory, and Computing (1978)), 283-292 · Zbl 0673.94027
[3] Capocelli, R. M.; Gargano, L.; Vaccaro, U., Time bounds for broadcasting in bounded degree graphs, (Workshop Graphtheoretical Concepts in Computer Science (1991)), 19-33 · Zbl 0768.68123
[4] Farley, A. M., Minimum broadcast networks, Networks, 9, 313-332 (1979) · Zbl 0425.94025
[5] Farley, A. M.; Hedetniemi, S. T., Broadcasting in grid graphs, (Proc. 9. S-E Conf. on Combinatorics, Graph Theory, and Computing (1978)), 275-288 · Zbl 0427.94044
[6] Farley, A. M.; Proskurowski, A., Broadcasting in trees with multiple originators, SIAM J. Algebraic Discrete Methods, 2, 381-386 (1981) · Zbl 0488.94044
[7] Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA) · Zbl 0411.68039
[8] Grigni, M.; Peleg, D., Tight bounds on minimum broadcast networks, SIAM J. Discerete Math., 4, 207-222 (1991) · Zbl 0725.94016
[9] Hedetniemi, S. M.; Hedetniemi, S. T.; Liestman, A. L., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1988) · Zbl 0649.90047
[10] Jakoby, A.; Reischuk, R.; Schindelhauer, C., Minimum Broadcast Time auf Graphen mit konstantem Grad, 18, (Workshop über Komplexitätstheorie und effiziente Algorithmen. Workshop über Komplexitätstheorie und effiziente Algorithmen, Forschungsbericht 92-17 (1992), Universität Trier)
[11] Krumme, D.; Cybenko, G.; Venkataraman, K. N., Gossiping in minimal time, SIAM J. Comput., 21, 111-139 (1992) · Zbl 0743.68039
[12] Lichtenstein, D., Planar formulae and their uses, SIAM J. Comput., 11, 320-343 (1982) · Zbl 0478.68043
[13] Liestman, A. L.; Peters, J. G., Broadcast networks of bounded degree, SIAM J. Discrete Math., 1, 531-540 (1988) · Zbl 0662.94027
[14] Middendorf, M., Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2, Inform. Process. Lett., 46, 281-287 (1993) · Zbl 0777.68027
[15] Rosenstiehl, P.; Tarjan, R. E., Rectilinear planar layouts of planar graphs and bipolar orientations, Discrete Comput. Geom., 1, 434-453 (1986) · Zbl 0607.05027
[16] Slater, P. J.; Cockayne, E. J.; Hedetniemi, S. T., Information dissemination in trees, SIAM J. Comput., 10, 692-701 (1981) · Zbl 0468.68064
[17] Tovey, C. A., A simplified NP-complete satisfiability problem, Discrete Appl. Math., 8, 85-89 (1984) · Zbl 0534.68028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.