Template-type: ReDif-Paper 1.0
Author-Name: Koster A.M.C.A.
Author-Name: Hoesel S.P.M. van
Author-Name: Kolen A.W.J.
Author-workplace-name: METEOR
Title: Solving frequency assignment problems via tree-decomposition
Abstract: In this paper we describe a computational study to solve hard frequency assignment problems (FAPs) to optimality using a tree decomposition of the graph that models interference constraints. We present a dynamic programming algorithm which solves FAPs based on this tree decomposition. We show that with the use of several dominance and bounding techniques it is possible to solve small and medium-size real-life instances of the frequency assignment problem to optimality. Moreover, with an iterative version of the algorithm we obtain good lower bounds for large-size instances within reasonable time and memory limits
Keywords: Economics ; 
Series: Research Memoranda
Creation-Date: 1999
Number: 036
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:3c2c1e5b-b6ba-461a-9863-06951789c1a1/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 460779
Handle: RePEc:unm:umamet:1999036