کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141869 | 957096 | 2011 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem](/preview/png/1141869.png)
In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation of the minimum-adjacency vertex coloring problem which, given an interference graph GG representing the potential interference between the antennas and a set of prespecified colors/channels, asks for a vertex coloring of GG minimizing the number of edges receiving adjacent colors. We propose an integer programming model for this problem and present three families of facet-inducing valid inequalities. Based on these results, we implement a branch-and-cut algorithm for this problem, and we provide promising computational results.
Journal: Discrete Optimization - Volume 8, Issue 4, November 2011, Pages 540–554