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...
Guardado en:
Autores principales: | , |
---|---|
Formato: | JOUR |
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15725286_v8_n4_p540_DelleDonne |
Aporte de: |
id |
todo:paper_15725286_v8_n4_p540_DelleDonne |
---|---|
record_format |
dspace |
spelling |
todo:paper_15725286_v8_n4_p540_DelleDonne2023-10-03T16:27:21Z A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem Delle Donne, D. Marenco, J. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, D. Marenco, J. 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. |
format |
JOUR |
author |
Delle Donne, D. Marenco, J. |
author_facet |
Delle Donne, D. Marenco, J. |
author_sort |
Delle Donne, D. |
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 |
url |
http://hdl.handle.net/20.500.12110/paper_15725286_v8_n4_p540_DelleDonne |
work_keys_str_mv |
AT delledonned abranchandcutalgorithmfortheminimumadjacencyvertexcoloringproblem AT marencoj abranchandcutalgorithmfortheminimumadjacencyvertexcoloringproblem AT delledonned branchandcutalgorithmfortheminimumadjacencyvertexcoloringproblem AT marencoj branchandcutalgorithmfortheminimumadjacencyvertexcoloringproblem |
_version_ |
1782030674825314304 |