A primal branch-and-cut algorithm for the degree-constrained minimum spanning tree problem

Beitrag in einem Sammelwerk
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Behle M, Jünger M, Liers F
Herausgeber: Camil Demetrescu
Titel Sammelwerk: Experimental Algorithms
Verlag: Springer
Verlagsort: Berlin Heidelberg
Jahr der Veröffentlichung: 2007
Titel der Reihe: Lecture Notes in Computer Science
Band: 4525
Seitenbereich: 379-392
ISBN: 9783540728443


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.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)


Einrichtungen weiterer Autorinnen und Autoren

Max Planck Institute for Informatics / Max-Planck-Institut für Informatik
Universität Köln


Zitierweisen

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: 

Zuletzt aktualisiert 2018-29-10 um 20:53