En:
Discrete Optim. 2011;8(4):540-554
Fecha:
2011
Formato:
application/pdf
Tipo de documento:
info:eu-repo/semantics/article
info:ar-repo/semantics/artículo
info:eu-repo/semantics/publishedVersion
info:ar-repo/semantics/artículo
info:eu-repo/semantics/publishedVersion
Descriptores:
Descripción:
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. © 2011 Elsevier B.V. All rights reserved.
Fil:Delle Donne, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
Fil:Delle Donne, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
Identificador(es):
Derechos:
info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by/2.5/ar
http://creativecommons.org/licenses/by/2.5/ar
Descargar texto: paper_15725286_v8_n4_p540_DelleDonne.oai
(tamaño kb)
![](../collect/artiaex/images/ipdf.gif)
Cita bibliográfica:
Delle Donne, D. (2011). A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem (info:eu-repo/semantics/article). [consultado: ] Disponible en el Repositorio Digital Institucional de la Universidad de Buenos Aires: <http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&cl=CL1&d=paper_15725286_v8_n4_p540_DelleDonne_oai>