Paper Info
Title
Elementary landscape decomposition of the frequency assignment problem
Abstract
The Frequency Assignment Problem (FAP) is an important problem that arises in the design of radio networks, when a channel has to be assigned to each transceiver of the network. This problem is a generalization of the graph coloring problem. In this paper we study a general version of the FAP that can include adjacent frequency constraints. Using concepts from landscapes' theory, we prove that this general FAP can be expressed as a sum of two elementary landscapes. Further analysis also shows that some subclasses of the problem correspond to a single elementary landscape. This allows us to compute the kind of neighborhood information that is normally associated with elementary landscapes. We also provide a closed form formula for computing the autocorrelation coefficient for the general FAP, which can be useful as an a priori indicator of the performance of a local search method.
Year
DOI
Venue
2011
10.1016/j.tcs.2011.02.011
Theor. Comput. Sci.
Keywords
DocType
Volume
Elementary landscapes,local search method,general version,Frequency Assignment Problem,adjacent frequency constraint,autocorrelation coefficient,elementary landscape decomposition,general FAP,Fitness landscapes,frequency assignment problem,Frequency assignment,elementary landscape,important problem,closed form formula,single elementary landscape
Journal
412
Issue
ISSN
Citations 
43
Theoretical Computer Science
5
PageRank 
References 
Authors
0.45
9
4
Name
Order
Citations
PageRank
Francisco Chicano150640.99
L. Darrell Whitley26631968.30
Enrique Alba33796242.34
Francisco Luna414412.40