A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

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

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.


Actions:
Download: [img] PDF - Preprinted Version
Download (112Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2007-531
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 19 Apr 2008 00:00
Last Modified: 06 Feb 2012 16:05
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/531