Abstract
Given a connected graph \(G=(V,E)\), the d-Minimum Branch Vertices (d-MBV) problem consists in finding a spanning tree of G with the minimum number of vertices with degree strictly greater than d. We developed a Miller–Tucker–Zemlin based formulation with valid inequalities for this problem. The results obtained for different values of d show the effectiveness of the proposed method, which has solved several instances faster than previous methods. Also, an heuristic is proposed for this problem, that was tested on several instances of the Minimum Branch Vertices problem, which is the d-MBV problem, when \(d = 2\).
Similar content being viewed by others
References
Akgün, İ., Tansel, B.Ç.: Min-degree constrained minimum spanning tree problem: new formulation via Miller–Tucker–Zemlin constraints. Comput. Oper. Res. 37(1), 72–82 (2010)
Bastos, L., Ochi, L.S., Protti, F., Subramanian, A., Martins, I., Pinheiro, R.G.S.: Efficient algorithms for cluster editing. J. Comb. Optim. 31(1), 347–371 (2016)
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)
Cerulli, R., Gentili, M., Iossa, A.: Bounded-degree spanning tree problems: models and new algorithms. Comput. Optim. Appl. 42(3), 353–370 (2009)
Coelho, V.N., Grasas, A., Ramalhinho, H., Coelho, I.M., Souza, M.J.F., Cruz, R.C.: An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints. Eur. J. Oper. Res. 250(2), 367–376 (2016)
Gargano, L., Hell, P., Stacho, L., Vaccaro, U.: Spanning trees with bounded number of branch vertices. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) Automata, Languages and Programming. ICALP 2002. Lecture Notes in Computer Science, vol. 2380. Springer, Berlin, Heidelberg (2002)
Landete, M., Marín, A., Sainz-Pardo, J.L.: Decomposition methods based on articulation vertices for degree-dependent spanning tree problems. Comput. Optim. Appl. 68(3), 749–773 (2017)
Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search: framework and applications. In: Gendreau, M., Potvin, J.Y. (eds.) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 146. Springer, Boston, MA (2010)
Marín, A.: Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem. Eur. J. Oper. Res. 245(3), 680–689 (2015)
Martinez, L.C., Da Cunha, A.S.: The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm. Discret. Appl. Math. 163, 210–224 (2014)
Melo, R.A., 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)
Merabet, M., Molnar, M.: Generalization of the Minimum Branch Vertices Spanning Tree Problem. PhD thesis, Nanyang Technological University, Singapore (2016)
Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM (JACM) 7(4), 326–329 (1960)
Schmidt, J.M.: A simple test on 2-vertex-and 2-edge-connectivity. Inf. Process. Lett. 113(7), 241–244 (2013)
Silva, D.M., Silva, R.M.A., Mateus, G.R., Gonçalves, J.F., Resende, M.G.C., Festa, P.: An iterative refinement algorithm for the minimum branch vertices problem. In: International Symposium on Experimental Algorithms, pp. 421–433. Springer, Heidelberg (2011)
Silva, R.M.A., Silva, D.M., Mateus, G.R., Gonçalves, J.F., Resende, M.G.C., Festa, P.: An edge-swap heuristic for generating spanning trees with minimum number of branch vertices. Optim. Lett. 8(4), 1225–1243 (2014)
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)
Sundar, S., Singh, A., Rossi, A.: New heuristics for two bounded-degree spanning tree problems. Inf. Sci. 195, 226–240 (2015)
Vilar, J.V., Arroyo, J.E.C.: ILS Heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness. J. Appl. Math. 1(1), 1–15 (2016)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Moreno, J., Frota, Y. & Martins, S. An exact and heuristic approach for the d-minimum branch vertices problem. Comput Optim Appl 71, 829–855 (2018). https://doi.org/10.1007/s10589-018-0027-x
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-018-0027-x