The complexity of finding a broadcast center. (English) Zbl 1498.68204
Wu, Weili (ed.) et al., Algorithmic aspects in information and management. 15th international conference, AAIM 2021, virtual event, December 20–22, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13153, 57-70 (2021).
Summary: Broadcasting in networks is one of the most important information dissemination processes. It is known that finding the optimal (minimum) broadcast time is NP-hard. Some of the follow-up researches focus on approximations/heuristics to find the broadcast center, a set of nodes from which the broadcast time in the network is minimum, in a given network by assuming the problem is hard without an actual proof. In this paper, we show that answering the questions “is a set of vertices a broadcast center to the given graph”, and “does the given graph has a broadcast center of size smaller than \(k\)” are both NP-hard under Turing reductions.
For the entire collection see [Zbl 1490.68034].
For the entire collection see [Zbl 1490.68034].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 90B18 | Communication networks in operations research |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Averbuch, A.; Shabtai, RH; Roditty, Y., Efficient construction of broadcast graphs, Discret. Appl. Math., 171, 9-14 (2014) · Zbl 1288.05133 · doi:10.1016/j.dam.2014.01.025 |
| [2] | Bar-Noy, A., Guha, S., Naor, J.S., Schieber, B.: Multicasting in heterogeneous networks. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, (STOC), pp. 448-453. ACM (1998) · Zbl 1028.68013 |
| [3] | Beier, R., Sibeyn, J.F.: A powerful heuristic for telephone gossiping. In: Proceedings of the 7th Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 17-35. Carleton Scientific (2000) |
| [4] | Bermond, J-C; Fraigniaud, P.; Peters, JG, Antepenultimate broadcasting, Networks, 26, 3, 125-137 (1995) · Zbl 0856.90046 · doi:10.1002/net.3230260302 |
| [5] | Bermond, J-C; Hell, P.; Liestman, AL; Peters, JG, Sparse broadcast graphs, Discret. Appl. Math., 36, 2, 97-130 (1992) · Zbl 0764.05042 · doi:10.1016/0166-218X(92)90226-Z |
| [6] | Dinneen, MJ; Ventura, JA; Wilson, MC; Zakeri, G., Compound constructions of broadcast networks, Discret. Appl. Math., 93, 2, 205-232 (1999) · Zbl 0941.90009 · doi:10.1016/S0166-218X(99)00043-8 |
| [7] | Elkin, M., Kortsarz, G.: Sublogarithmic approximation for telephone multicast: path out of jungle (extended abstract). In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 76-85. Society for Industrial and Applied Mathematics (2003) · Zbl 1094.68515 |
| [8] | Elkin, M.; Kortsarz, G., A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem, SIAM J. Comput., 35, 3, 672-689 (2005) · Zbl 1095.68130 · doi:10.1137/S0097539704440740 |
| [9] | Farley, AM, Minimal broadcast networks, Networks, 9, 4, 313-332 (1979) · Zbl 0425.94025 · doi:10.1002/net.3230090404 |
| [10] | Farley, AM; Hedetniemi, S.; Mitchell, S.; Proskurowski, A., Minimum broadcast graphs, Discret. Math., 25, 2, 189-193 (1979) · Zbl 0404.05038 · doi:10.1016/0012-365X(79)90022-0 |
| [11] | Fraigniaud, P.; Lazard, E., Methods and problems of communication in usual networks, Discret. Appl. Math., 53, 1-3, 79-133 (1994) · Zbl 0818.94029 · doi:10.1016/0166-218X(94)90180-5 |
| [12] | Garey, MR; Johnson, DS, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), New York: W.H. Freeman, New York · Zbl 0411.68039 |
| [13] | Gargano, L.; Vaccaro, U., On the construction of minimal broadcast networks, Networks, 19, 6, 673-689 (1989) · Zbl 0676.90021 · doi:10.1002/net.3230190606 |
| [14] | Grigni, M.; Peleg, D., Tight bounds on mimimum broadcast networks, SIAM J. Discret. Math., 4, 2, 207-222 (1991) · Zbl 0725.94016 · doi:10.1137/0404021 |
| [15] | Grigoryan, H.; Harutyunyan, HA; Gu, Q.; Hell, P.; Yang, B., New lower bounds on broadcast function, Algorithmic Aspects in Information and Management, 174-184 (2014), Cham: Springer, Cham · Zbl 1359.05116 · doi:10.1007/978-3-319-07956-1_16 |
| [16] | Harutyunyan, HA; Gu, Q.; Hell, P.; Yang, B., Broadcast networks with near optimal cost, Algorithmic Aspects in Information and Management, 312-322 (2014), Cham: Springer, Cham · Zbl 1359.68018 · doi:10.1007/978-3-319-07956-1_28 |
| [17] | Harutyunyan, HA; Li, Z.; Du, D-Z; Duan, Z.; Tian, C., A simple construction of broadcast graphs, Computing and Combinatorics, 240-253 (2019), Cham: Springer, Cham · Zbl 1534.68167 · doi:10.1007/978-3-030-26176-4_20 |
| [18] | Harutyunyan, HA; Li, Z., A new construction of broadcast graphs, Discret. Appl. Math., 280, 144-155 (2020) · Zbl 1439.05127 · doi:10.1016/j.dam.2018.09.015 |
| [19] | Harutyunyan, HA; Liestman, AL, More broadcast graphs, Discret. Appl. Math., 98, 1, 81-102 (1999) · Zbl 0936.05059 · doi:10.1016/S0166-218X(99)00108-0 |
| [20] | Harutyunyan, HA; Liestman, AL, Upper bounds on the broadcast function using minimum dominating sets, Discret. Math., 312, 20, 2992-2996 (2012) · Zbl 1252.05161 · doi:10.1016/j.disc.2012.06.016 |
| [21] | Harutyunyan, H.A., Liestman, A.L., Peters, J.G., Richards, D.: Broadcasting and gossiping. In: Handbook of Graph Theory, pp. 1477-1494. Chapman and Hall (2013) |
| [22] | Harutyunyan, HA; Liestman, AL; Shao, B., A linear algorithm for finding the k-broadcast center of a tree, Networks, 53, 3, 287-292 (2009) · Zbl 1175.68295 · doi:10.1002/net.20270 |
| [23] | Harutyunyan, H.; Maraachlian, E.; Lin, G., Linear algorithm for broadcasting in unicyclic graphs, Computing and Combinatorics, 372-382 (2007), Heidelberg: Springer, Heidelberg · Zbl 1206.68236 · doi:10.1007/978-3-540-73545-8_37 |
| [24] | Harutyunyan, HA; Maraachlian, E., On broadcasting in unicyclic graphs, J. Comb. Optim., 16, 3, 307-322 (2008) · Zbl 1165.94304 · doi:10.1007/s10878-008-9160-2 |
| [25] | Hedetniemi, SM; Hedetniemi, ST; Liestman, AL, A survey of gossiping and broadcasting in communication networks, Networks, 18, 4, 319-349 (1988) · Zbl 0649.90047 · doi:10.1002/net.3230180406 |
| [26] | Hromkovič, J.; Klasing, R.; Monien, B.; Peine, R.; Du, DZ; Hsu, DF, Dissemination of Information in Interconnection Networks (Broadcasting & Gossiping), Combinatorial Network Theory, 125-212 (1996), Boston: Springer, Boston · Zbl 0840.68088 · doi:10.1007/978-1-4757-2491-2_5 |
| [27] | Čevnik, M.; Žerovnik, J., Broadcasting on cactus graphs, J. Comb. Optim., 33, 1, 292-316 (2015) · Zbl 1365.05268 · doi:10.1007/s10878-015-9957-8 |
| [28] | Maheo, M.; Saclé, J-F, Some minimum broadcast graphs, Discret. Appl. Math., 53, 1-3, 275-285 (1994) · Zbl 0807.94028 · doi:10.1016/0166-218X(94)90190-2 |
| [29] | Slater, PJ; Cockayne, EJ; Hedetniemi, ST, Information dissemination in trees, SIAM J. Comput., 10, 4, 692-701 (1981) · Zbl 0468.68064 · doi:10.1137/0210052 |
| [30] | Su, Y-H; Lin, C-C; Lee, DT; Thai, MT; Sahni, S., Broadcasting in heterogeneous tree networks, Computing and Combinatorics, 368-377 (2010), Heidelberg: Springer, Heidelberg · Zbl 1286.68013 · doi:10.1007/978-3-642-14031-0_40 |
| [31] | Zhou, J.; Zhang, K., A minimum broadcast graph on 26 vertices, Appl. Math. Lett., 14, 8, 1023-1026 (2001) · Zbl 0983.05054 · doi:10.1016/S0893-9659(01)00082-9 |
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.
