A branch‐and‐cut algorithm for the minimum‐adjacency vertex coloring problem

A branch‐and‐cut algorithm for the minimum‐adjacency vertex coloring problem

0.00 Avg rating0 Votes
Article ID: iaor201110073
Volume: 8
Issue: 4
Start Page Number: 540
End Page Number: 554
Publication Date: Nov 2011
Journal: Discrete Optimization
Authors: ,
Keywords: networks, graphs
Abstract:

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 G representing the potential interference between the antennas and a set of prespecified colors/channels, asks for a vertex coloring of G 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.

Reviews

Required fields are marked *. Your email address will not be published.