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

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 i...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Delle Donne, Diego, Marenco, Javier Leonardo
Publicado: 2011
Materias:
Adjacent colors
Frequency assignment
Integer programming
Adjacent channels
Branch-and-cut algorithms
Computational results
Frequency assignments
Frequency channels
Integer programming models
Interference graphs
Potential interferences
Valid inequality
Vertex coloring
Vertex coloring problems
Wireless communication network
Algorithms
Antennas
Cochannel interference
Combinatorial optimization
Computer programming
Graph theory
Wireless networks
Wireless telecommunication systems
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v8_n4_p540_DelleDonne
http://hdl.handle.net/20.500.12110/paper_15725286_v8_n4_p540_DelleDonne
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_15725286_v8_n4_p540_DelleDonne
record_format dspace
spelling paper:paper_15725286_v8_n4_p540_DelleDonne2023-06-08T16:24:40Z A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem Delle Donne, Diego Marenco, Javier Leonardo Adjacent colors Frequency assignment Integer programming Adjacent channels Adjacent colors Branch-and-cut algorithms Computational results Frequency assignments Frequency channels Integer programming models Interference graphs Potential interferences Valid inequality Vertex coloring Vertex coloring problems Wireless communication network Algorithms Antennas Cochannel interference Combinatorial optimization Computer programming Graph theory Wireless networks Wireless telecommunication systems Integer programming 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. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v8_n4_p540_DelleDonne http://hdl.handle.net/20.500.12110/paper_15725286_v8_n4_p540_DelleDonne
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Adjacent colors
Frequency assignment
Integer programming
Adjacent channels
Adjacent colors
Branch-and-cut algorithms
Computational results
Frequency assignments
Frequency channels
Integer programming models
Interference graphs
Potential interferences
Valid inequality
Vertex coloring
Vertex coloring problems
Wireless communication network
Algorithms
Antennas
Cochannel interference
Combinatorial optimization
Computer programming
Graph theory
Wireless networks
Wireless telecommunication systems
Integer programming
spellingShingle Adjacent colors
Frequency assignment
Integer programming
Adjacent channels
Adjacent colors
Branch-and-cut algorithms
Computational results
Frequency assignments
Frequency channels
Integer programming models
Interference graphs
Potential interferences
Valid inequality
Vertex coloring
Vertex coloring problems
Wireless communication network
Algorithms
Antennas
Cochannel interference
Combinatorial optimization
Computer programming
Graph theory
Wireless networks
Wireless telecommunication systems
Integer programming
Delle Donne, Diego
Marenco, Javier Leonardo
A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
topic_facet Adjacent colors
Frequency assignment
Integer programming
Adjacent channels
Adjacent colors
Branch-and-cut algorithms
Computational results
Frequency assignments
Frequency channels
Integer programming models
Interference graphs
Potential interferences
Valid inequality
Vertex coloring
Vertex coloring problems
Wireless communication network
Algorithms
Antennas
Cochannel interference
Combinatorial optimization
Computer programming
Graph theory
Wireless networks
Wireless telecommunication systems
Integer programming
description 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.
author Delle Donne, Diego
Marenco, Javier Leonardo
author_facet Delle Donne, Diego
Marenco, Javier Leonardo
author_sort Delle Donne, Diego
title A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
title_short A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
title_full A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
title_fullStr A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
title_full_unstemmed A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
title_sort branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
publishDate 2011
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v8_n4_p540_DelleDonne
http://hdl.handle.net/20.500.12110/paper_15725286_v8_n4_p540_DelleDonne
work_keys_str_mv AT delledonnediego abranchandcutalgorithmfortheminimumadjacencyvertexcoloringproblem
AT marencojavierleonardo abranchandcutalgorithmfortheminimumadjacencyvertexcoloringproblem
AT delledonnediego branchandcutalgorithmfortheminimumadjacencyvertexcoloringproblem
AT marencojavierleonardo branchandcutalgorithmfortheminimumadjacencyvertexcoloringproblem
_version_ 1768545757558734848

Ejemplares similares