  


Facets of the minimumadjacency vertex coloring polytope
Diego Delle Donne(ddelledoungs.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, cochannel 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 minimumadjacency 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 facetinducing valid inequalities. Keywords: frequency assignment, adjacent colors, integer programming Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Integer Programming (01 Programming ) Citation: Technical Report, Universidad Nacional de General Sarmiento, October 2010. Download: [PDF] Entry Submitted: 10/01/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  