×

The generalized minimum branch vertices problem: properties and polyhedral analysis. (English) Zbl 1469.90091

Summary: This article introduces the Generalized Minimum Branch Vertices problem. Given an undirected graph, where the set of vertices is partitioned into clusters, the Generalized Minimum Branch Vertices problem consists of finding a tree spanning exactly one vertex for each cluster and having the minimum number of branch vertices, namely vertices with degree greater than two. When each cluster is a singleton, the problem reduces to the well-known Minimum Branch Vertices problem, which is NP-hard. We show some properties that any feasible solution to the problem has to satisfy. Some of these properties can be used to determine useless vertices or edges, which can be removed to reduce the size of the instances. We propose an integer linear programming formulation for the problem, we derive the dimension of the polytope, we study the trivial inequalities and introduce two new classes of valid inequalities, that are proved to be facet-defining.

MSC:

90C10 Integer programming
90C35 Programming involving graphs or networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gargano, L.; Hell, P.; Stacho, L.; Vaccaro, U., Spanning Trees with Bounded Number of Branch Vertices, 355-365 (2002), Berlin Heidelberg: Springer, Berlin Heidelberg · Zbl 1056.68587
[2] 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
[3] 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
[4] 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
[5] Merabet, M., Molnár, M.: Generalization of the Minimum Branch Vertices Spanning Tree Problem. Research report, Nanyang Technological University, Singapore (2016) · Zbl 1403.90582
[6] Debiasio, L.; Lo, A., Spanning trees with few branch vertices, SIAM J. Discret. Math., 33, 1 (2017) · Zbl 1419.05044
[7] Feremans, C.; Labbé, M.; Letchford, AN; Salazar-González, JJ, Generalized network design polyhedra, Networks, 58, 2, 125-136 (2011) · Zbl 1233.90066 · doi:10.1002/net.20455
[8] Myung, YS; Lee, CH; Tcha, DW, On the generalized minimum spanning tree problem, Networks, 26, 4, 231-241 (1995) · Zbl 0856.90117 · doi:10.1002/net.3230260407
[9] Feremans, C.; Labbé, M.; Laporte, G., A comparative analysis of several formulations for the generalized minimum spanning tree problem, Networks, 39, 1, 29-34 (2002) · Zbl 1001.90066 · doi:10.1002/net.10009
[10] Feremans, C.; Labbé, M.; Laporte, G., The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm, Networks, 43, 2, 71-86 (2004) · Zbl 1069.68114 · doi:10.1002/net.10105
[11] Fischetti, M.; González, JJS; Toth, P., The symmetric generalized traveling salesman polytope, Networks, 26, 2, 113-123 (1995) · Zbl 0856.90116 · doi:10.1002/net.3230260206
[12] Fischetti, M.; González, JJS; Toth, P., A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Oper. Res., 45, 3, 378-394 (1997) · Zbl 0893.90164 · doi:10.1287/opre.45.3.378
[13] Noronha, TF; Ribeiro, CC, Routing and wavelength assignment by partition colouring, Eur. J. Oper. Res., 171, 3, 797-810 (2006) · Zbl 1116.90073 · doi:10.1016/j.ejor.2004.09.007
[14] Demange, M.; Ekim, T.; Ries, B.; Tanasescu, C., On some applications of the selective graph coloring problem, Eur. J. Oper. Res., 240, 2, 307-314 (2015) · Zbl 1357.05041 · doi:10.1016/j.ejor.2014.05.011
[15] Fidanova, S.; Pop, P., An improved hybrid ant-local search algorithm for the partition graph coloring problem, J. Comput. Appl. Math., 293, 55-61 (2016) · Zbl 1334.90187 · doi:10.1016/j.cam.2015.04.030
[16] Frota, Y.; Maculan, N.; Noronha, TF; Ribeiro, CC, A branch-and-cut algorithm for partition coloring, Networks, 55, 3, 194-204 (2010) · Zbl 1205.05089
[17] Pop, PC; Hu, B.; Raidl, GR; Moreno-Díaz, R.; Pichler, F.; Quesada-Arencibia, A., A memetic algorithm with two distinct solution representations for the partition graph coloring problem, Computer Aided Systems Theory - EUROCAST 2013, 219-226 (2013), Berlin: Springer, Berlin · doi:10.1007/978-3-642-53856-8_28
[18] Dashti, Y., Mercian, A., Reisslein, M.: Evaluation of dynamic bandwidth allocation with clustered routing in fiwi networks. In: 2014 IEEE 20th International Workshop on Local Metropolitan Area Networks (LANMAN), pp. 1-6 (2014)
[19] Nemhauser, G.; Wolsey, L., Integer and Combinatorial optimization (2014), New York, NY: Wiley, New York, NY · Zbl 0944.90001
[20] Diestel, R., Graph Theory Graduate Texts in Mathematics; 173 (2000), Berlin: Springer, Berlin · Zbl 0945.05002
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.