Optimization Online


Facets of the minimum-adjacency vertex coloring polytope

Diego Delle Donne(ddelledo***at***ungs.edu.ar)
Javier Marenco(jmarenco***at***ungs.edu.ar)

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 two families of facet-inducing valid inequalities.

Keywords: frequency assignment, adjacent colors, integer programming

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (0-1 Programming )

Citation: Technical Report, Universidad Nacional de General Sarmiento, October 2010.

Download: [PDF]

Entry Submitted: 10/01/2010
Entry Accepted: 10/01/2010
Entry Last Modified: 10/01/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society