Universität zu Köln

Behle, Markus, Jünger, Michael and Liers, Frauke (2007). A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem. In: Experimental algorithms : 6th international workshop ; proceedings / WEA 2007, Rome, Italy, June 6 - 8, pp. 379-392. Springer.

Preview

PDF zaik2007-531.pdf - Draft Version Download (114kB) | Preview

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.

Item Type:	Book Section, Proceedings Item or annotation in a legal commentary
Creators:	Creators Email ORCID ORCID Put Code Behle, Markus UNSPECIFIED UNSPECIFIED UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Liers, Frauke UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549054
Title of Book:	Experimental algorithms : 6th international workshop ; proceedings / WEA 2007, Rome, Italy, June 6 - 8
Series Name:	Lecture Notes in Computer Science
Volume:	4525
Page Range:	pp. 379-392
Date:	2007
Publisher:	Springer
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54905