Spanning trees with few branch vertices in graphs of bounded neighborhood diversity. (English) Zbl 07786533
Rajsbaum, Sergio (ed.) et al., Structural information and communication complexity. 30th international colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6–9, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13892, 502-519 (2023).
Summary: A branch vertex in a tree is a vertex of degree at least three. We study the NP-hard problem of constructing spanning trees with as few branch vertices as possible. This problem generalizes the famous Hamiltonian Path problem which corresponds to the case of no vertices having degree three or more. It has been extensively studied in the literature and has important applications in network design and optimization. In this paper, we study the problem of finding a spanning tree with the minimum number of branch vertices in graphs of bounded neighborhood diversity. Neighborhood diversity, a generalization of vertex cover to dense graphs, plays an important role in the design of algorithms for such graphs.
For the entire collection see [Zbl 1528.68034].
For the entire collection see [Zbl 1528.68034].
MSC:
| 68Mxx | Computer system organization |
| 68Q11 | Communication complexity, information complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Agrawal, A., Parameterized complexity of happy coloring problems, Theoret. Comput. Sci., 835, 58-81 (2020) · Zbl 1460.68046 · doi:10.1016/j.tcs.2020.06.002 |
| [2] | Araujo, J.; Ducoffe, G.; Nisse, N.; Suchan, K., On interval number in cycle convexity, Discrete Math. Theoret. Comput. Sci., 20, 1, 1-28 (2018) · Zbl 1401.05208 |
| [3] | Watel, D., Baste, J.: An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth. Available at SSRN: https://ssrn.com/abstract=4197048 or doi:10.2139/ssrn.4197048 |
| [4] | Bermond, J-C; Gargano, L.; Rescigno, AA; Shvartsman, AA; Felber, P., Gathering with minimum delay in tree sensor networks, Structural Information and Communication Complexity, 262-276 (2008), Heidelberg: Springer, Heidelberg · Zbl 1143.68334 · doi:10.1007/978-3-540-69355-0_22 |
| [5] | Bermond, J-C; Gargano, L.; Rescigno, AA, Gathering with minimum completion time in sensor tree networks, J. Interconnect. Netw., 11, 1-33 (2010) · doi:10.1142/S0219265910002714 |
| [6] | Bermond, J-C; Gargano, L.; Peénnes, S.; Rescigno, AA; Vaccaro, U., Optimal time data gathering in wireless networks with multidirectional antennas, Theoret. Comput. Sci., 509, 122-139 (2013) · Zbl 1358.68048 · doi:10.1016/j.tcs.2013.03.017 |
| [7] | Bhyravarapu, S., Reddy, I.V.: On structural parameterizations of star coloring. arXiv preprint: arXiv:2211.12226 (2022) · Zbl 07728660 |
| [8] | Bianzino, AP; Chaudet, C.; Rossi, D.; Rougier, JL, A survey of green networking research, IEEE Commun. Surv. Tutorials, 14, 3-20 (2012) · doi:10.1109/SURV.2011.113010.00106 |
| [9] | Carrabs, F.; Cerulli, R.; Gaudioso, M.; Gentili, M., Lower and upper bounds for the spanning tree with minimum branch vertices, Comput. Optim. Appl., 56, 2, 405-438 (2013) · Zbl 1312.90038 · doi:10.1007/s10589-013-9556-5 |
| [10] | Celik, A.; Kamal, AE, Green cooperative spectrum sensing and scheduling in heterogeneous cognitive radio networks, IEEE Trans. Cognitive Commun. Networking, 2, 238-248 (2016) · doi:10.1109/TCCN.2016.2608337 |
| [11] | Cerrone, C.; Cerulli, R.; Raiconi, A., Relations, models and a memetic approach for three degree-dependent spanning tree problems, Eur. J. Oper. Res., 232, 3, 442-453 (2014) · Zbl 1305.90346 · doi:10.1016/j.ejor.2013.07.029 |
| [12] | Cerulli, R.; Gentili, M.; Iossa, A., Bounded-degree spanning tree problems: models and new algorithms, Comput. Optim. Appl., 42, 3, 353-370 (2009) · Zbl 1211.90259 · doi:10.1007/s10589-007-9120-2 |
| [13] | Chimani, VM; Spoerhase, J., Approximating spanning trees with few branches, Theory Comput. Syst., 56, 1, 181-196 (2015) · Zbl 1328.68297 · doi:10.1007/s00224-014-9556-6 |
| [14] | Cordasco, G.; Gargano, L.; Rescigno, AA; Vaccaro, U., Evangelism in social networks: algorithms and complexity, Networks, 71, 4, 346-357 (2018) · Zbl 1396.91606 · doi:10.1002/net.21756 |
| [15] | Cordasco, G.; Gargano, L.; Rescigno, AA; Gąsieniec, L.; Klasing, R.; Radzik, T., Iterated type partitions, Combinatorial Algorithms, 195-210 (2020), Cham: Springer, Cham · Zbl 07601008 · doi:10.1007/978-3-030-48966-3_15 |
| [16] | Cordasco, G., Gargano, L., Rescigno, A.A.: Parameterized complexity of immunization in the threshold model. In: Mutzel, P., Rahman, M.S., Slamin (eds.) WALCOM: Algorithms and Computation. WALCOM 2022. Lecture Notes in Computer Science(), vol. 13174. Springer, Cham (2022). doi:10.1007/978-3-030-96731-4_23 · Zbl 07556578 |
| [17] | Courcelle, B.; Olariu, S., Upper bounds to the clique width of graphs, Discret. Appl. Math., 101, 1-3, 77-144 (2000) · Zbl 0958.05105 · doi:10.1016/S0166-218X(99)00184-5 |
| [18] | Cygan, M., Lower bounds for kernelization, Parameterized Algorithms, 523-555 (2015), Cham: Springer, Cham · doi:10.1007/978-3-319-21275-3_15 |
| [19] | Downey, RG; Fellows, MR, Parameterized Complexity (1999), New York: Springer-Verlag, New York · doi:10.1007/978-1-4612-0515-9 |
| [20] | Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Clique-width: on the price of generality. In: Proceedings of SODA 2009, pp. 825-834 (2009) · Zbl 1421.68125 |
| [21] | Fomin, FV; Golovach, PA; Lokshtanov, D.; Saurabh, S., Intractability of clique-width parameterizations, SIAM J. Comput., 39, 5, 1941-1956 (2010) · Zbl 1207.68161 · doi:10.1137/080742270 |
| [22] | Gajarsky, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) Parameterized and Exact Computation. IPEC 2013. Lecture Notes in Computer Science, vol. 8246. Springer, Cham (2013). doi:10.1007/978-3-319-03898-8_15 · Zbl 1406.68080 |
| [23] | Ganian, R.: Using neighborhood diversity to solve hard problems (2012). arXiv:1201.3091 |
| [24] | Gargano, L.; Hammar, M.; Hell, P.; Stacho, L.; Vaccaro, U., Spanning spiders and light splitting switches, Discret. Math., 285, 1, 83-95 (2004) · Zbl 1044.05048 · doi:10.1016/j.disc.2004.04.005 |
| [25] | Gargano, L.; Hell, P.; Stacho, L.; Vaccaro, U.; Widmayer, P.; Eidenbenz, S.; Triguero, F.; Morales, R.; Conejo, R.; Hennessy, M., Spanning trees with bounded number of branch vertices, Automata, Languages and Programming, 355-365 (2002), Heidelberg: Springer, Heidelberg · Zbl 1056.68587 · doi:10.1007/3-540-45465-9_31 |
| [26] | Gargano, L.; Rescigno, AA, Complexity of conflict-free colorings of graphs, Theoret. Comput. Sci., 566, 39-49 (2015) · Zbl 1317.68071 · doi:10.1016/j.tcs.2014.11.029 |
| [27] | Gargano, L.; Rescigno, AA, Collision-free path coloring with application to minimum-delay gathering in sensor networks, Discret. Appl. Math., 157, 8, 1858-1872 (2009) · Zbl 1198.68181 · doi:10.1016/j.dam.2009.01.015 |
| [28] | Gavenciak, T.; Koutecký, M.; Knop, D., Integer programming in parameterized complexity: five miniatures, Discrete Optim., 44 (2022) · Zbl 1510.90185 · doi:10.1016/j.disopt.2020.100596 |
| [29] | Gozupek, D.; Buhari, S.; Alagoz, F., A spectrum switching delay-aware scheduling algorithm for centralized cognitive radio networks, IEEE Trans. Mobile Comp., 12, 1270-1280 (2013) · doi:10.1109/TMC.2012.101 |
| [30] | Jansen, K., Rohwedderb, L.: On integer programming, discrepancy, and convolution. Math. Operat. Res., 1-15 (2023) |
| [31] | Lampis, M., Algorithmic meta-theorems for restrictions of treewidth, Algorithmica, 64, 19-37 (2012) · Zbl 1252.68154 · doi:10.1007/s00453-011-9554-x |
| [32] | Landete, M.; Marín, A.; Sainz-Pardo, JL, Decomposition methods based on articulation vertices for degree-dependent spanning tree problems, Comput. Optim. Appl., 68, 3, 749-773 (2017) · Zbl 1394.90547 · doi:10.1007/s10589-017-9924-7 |
| [33] | Marin, A., Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem, Eur. J. Oper. Res., 245, 3, 680-689 (2015) · Zbl 1346.90789 · doi:10.1016/j.ejor.2015.04.011 |
| [34] | Melo, RA; Samer, P.; Urrutia, S., An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices, Comput. Optim. Appl., 65, 3, 821-844 (2016) · Zbl 1357.90123 · doi:10.1007/s10589-016-9850-0 |
| [35] | Matsuda, H.; Ozeki, K.; Yamashita, T., Spanning trees with a bounded number of branch vertices in a claw-free graph, Graphs and Combinatorics, 30, 429-437 (2014) · Zbl 1298.05074 · doi:10.1007/s00373-012-1277-5 |
| [36] | Robertson, N.; Seymour, PD, Graph minors II. algorithmic aspects of tree-width, J. Algorithms, 7, 309-322 (1986) · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4 |
| [37] | Rossi, A.; Singh, A.; Shyam, S., Cutting-plane-based algorithms for two branch vertices related spanning tree problems, Optim. Eng., 15, 855-887 (2014) · Zbl 1364.90335 · doi:10.1007/s11081-013-9219-5 |
| [38] | Salamon, G.: Spanning tree optimization problems with degree-based objective functions. In: 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 309-315 (2005) |
| [39] | Shami, N., Rasti, M.: A joint multi-channel assignment and power control scheme for energy efficiency in cognitive radio networks. In: Proceedings IEEE Wireless Communications and Networking Conference, WCNC 2016, pp. 1-6 (2016) |
| [40] | Silva, RMA; Silva, DM; Resende, MGC; Mateus, GR; Goncalves, JF; Festa, P., An edge-swap heuristic for generating spanning trees with minimum number of branch vertices, Optim. Lett., 8, 4, 1225-1243 (2014) · Zbl 1292.90305 · doi:10.1007/s11590-013-0665-y |
| [41] | Silvestri, S.; Laporte, G.; Cerulli, R., A branch-and-cut algorithm for the minimum branch vertices spanning tree problem, Comput. Oper. Res., 81, 322-332 (2017) · Zbl 1391.90619 · doi:10.1016/j.cor.2016.11.010 |
| [42] | Sundar, S.; Singh, A.; Rossi, A., New heuristics for two bounded-degree spanning tree problems, Inf. Sci., 195, 226-240 (2012) · doi:10.1016/j.ins.2012.01.037 |
| [43] | Toufar, T., Masařík, T., Koutecký, M., Knop, D.: Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. Log. Methods Comput. Sci. 15 (2019) · Zbl 1427.68125 |
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.
