A primal branch-and-cut algorithm for the degree-constrained minimum spanning tree problem
Behle M, Jünger M, Liers F (2007)
Publication Status: Published
Publication Type: Book chapter / Article in edited volumes
Publication year: 2007
Publisher: Springer
Edited Volumes: Experimental Algorithms
Series: Lecture Notes in Computer Science
City/Town: Berlin Heidelberg
Book Volume: 4525
Pages Range: 379-392
Event location: Rome
ISBN: 9783540728443
DOI: 10.1007/978-3-540-72845-0_29
Abstract
The degree-constrained minimum spanning tree (DCMST) is relevant in the design of networks. It consists of finding a spanning tree whose nodes do not exceed a given maximum degree and whose total edge length is minimum. We design a primal branch-and-cut algorithm that solves instances of the problem to optimality. Primal methods have not been used extensively in the past, and their performance often could not compete with their standard 'dual' counterparts. We show that primal separation procedures yield good bounds for the DCMST problem. On several instances, the primal branch-and-cut program turns out to be competitive with other methods known in the literature. This shows the potential of the primal method. © Springer-Verlag Berlin Heidelberg 2007.
Authors with CRIS profile
Involved external institutions
Max Planck Institute for Informatics / Max-Planck-Institut für Informatik
Germany (DE)
Universität zu Köln
Germany (DE)
Germany (DE)
Universität zu Köln
Germany (DE)
How to cite
APA:
Behle, M., Jünger, M., & Liers, F. (2007). A primal branch-and-cut algorithm for the degree-constrained minimum spanning tree problem. In Camil Demetrescu (Eds.), Experimental Algorithms. (pp. 379-392). Berlin Heidelberg: Springer.
MLA:
Behle, Markus, Michael Jünger, and Frauke Liers. "A primal branch-and-cut algorithm for the degree-constrained minimum spanning tree problem." Experimental Algorithms. Ed. Camil Demetrescu, Berlin Heidelberg: Springer, 2007. 379-392.
BibTeX: Download