Solving Frequency Assignment Problems via Tree-Decomposition1

✍ Scribed by Arie M.C.A. Koster; Stan P.M. van Hoesel; Antoon W.J. Kolen

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 69 KB
• Volume: 3
• Category: Article
• ISSN: 1571-0653
• DOI: 10.1016/s1571-0653(05)80034-4

✦ Synopsis

In this extended abstract 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. 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.