Minimum Diameter Trees Subject to a Budget Constraint

• Amanda Ferreira de Azevedo UFRJ
• Abilio Lucena UFRJ

DOI: https://doi.org/10.5753/etc.2023.230704

Resumo

Formulations are proposed for problems that ask for minimum diameter trees of an undirected graph, subject to an upper bound on the sum of their edge costs. The problems, namely the Budget Restricted Minimum Diameter Spanning Tree, the Budget Restricted Minimum Diameter Steiner Tree, and the Budget Restricted Minimum Diameter Terminal Steiner Tree, represent challenging extensions for three intensively investigated NP-hard problems. Furthermore practical applications for these extensions naturally carry over from those for the problems they originate from. Three distinct types of formulations are proposed here for each of the previously indicated problem extensions. Computational results for these formulations will be presented separately.

Referências

Cheng, X., Li, Y., Du, D.-Z., and Ngo, H. Q. (2004). Steiner trees in industry. Handbook of Combinatorial Optimization, pages 193–216.

Dantzig, G., Fulkerson, R., and Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. https://doi.org/10.1287/opre.2.4.393, 2:393–410.

Desrochers, M. and Laporte, G. (1991). Improvements and extensions to the miller-tucker-zemlin subtour elimination constraints. Operations Research Letters, 10:27–36.

Ding, W. and Qiu, K. (2014). Algorithms for the minimum diameter terminal Steiner tree problem. Journal of Combinatorial Optimization, 28(4):837–853.

Dos Santos, A. C., Lucena, A., and Ribeiro, C. C. (2004). Solving diameter constrained minimum spanning tree problems in dense graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3059:458–467.

Goemans, M. X. and Myung, Y.-S. (1993). A catalog of Steiner tree formulations. Networks, 23(1):19–28.

Gouveia, L. and Magnanti, T. L. (2003). Network Flow Models for Designing Diameter-Constrained Minimum-Spanning and Steiner Trees. Networks, 41(3):159–173.

Gouveia, L., Simonetti, L., and Uchoa, E. (2011). Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. Mathematical Programming, 128(1-2):123–148.

Handler, G. Y. (1973). Minimax Location of a Facility in an Undirected tree graph. Transportation Science, 7(3):287–293.

Ivanov, A., Tuzhilin, A., and Cieslik, D. (2003). Steiner ratio for manifolds. Mathematical Notes, 74:367–374.

Lin, G. and Xue, G. (2002). On the terminal Steiner tree problem. Information Processing Letters, 84(2):103–107.

Lu, C. L., Tang, C. Y., and Lee, R. C. T. (2003). The full Steiner tree problem. Theoretical Computer Science, 306(1-3):55–67.

Maculan, N. (1987). The Steiner problem in graphs. Annals of Discrete Mathematics, 31:185 – 212.

Marathe, M. V., Ravi, R., Sundaram, R., Ravi, S. S., Rosenkrantz, D. J., and Hunt, H. B. (1998). Bicriteria network design problems. Journal of Algorithms, 28:142–171.

Miller, C. E., Zemlin, R. A., and Tucker, A. W. (1960). Integer Programming Formulation of Traveling Salesman Problems. Journal of the ACM (JACM), 7(4):326–329.

Mondaini, R. P. (2008). The Steiner tree problem and its application to the modelling of biomolecular structures. Mathematical Modelling of Biosystems, pages 199–219.

Plesnik, J. (1981). The complexity of designing a network with minimum diameter. Networks, 11(1):77–85.

Robins, G. and Zelikovsky, A. (2008). Minimum Steiner tree construction. Handbook of Algorithms for Physical Design Automation.

Smith, J. M. (1998). Steiner minimal trees in e 3: Theory, algorithms, and applications. Handbook of Combinatorial Optimization, pages 1143–1216.

Smith, J. M. and Gross, M. (1982). Steiner minimal trees and urban service networks. Socio-Economic Planning Sciences, 16:21–38.