B-coloring is a problem in graph theory at the basis of several real applications and also used to improve solution methods for the classical coloring problem. Enhanced solutions for the classical coloring problem have in turn impacts on several other practical applications in scheduling, timetabling and telecommunications. Namely, given a graph G = (V, E), the b-coloring problem consists of maximizing the number of colors used while assigning a color to every vertex in V such that no pair of adjacent vertices receive the same color and every color has a representative, called a b-vertex. A vertex can be a b-vertex if it is adjacent to vertices colored with all the colors apart from the one assigned to it. In this paper we present a novel Iterative Matheuristic Algorithm based on considerations about the structure of promising solutions and a mathematical programming model. A vast section of computational experiments shows how the approach is able to find high quality solutions for commonly established datasets from the literature. In particular, the method we propose is able to improve the best known heuristic solution for 38 instances of the 137 considered. The optimality of the bounds previously known for another 5 instances has also been proved by running the approach we propose exhaustively.

An Iterative Matheuristic Algorithm for the B-Coloring Problem / Montemanni, R.; Smith, D. H.. - (2022), pp. 265-270. ((Intervento presentato al convegno 3rd International Conference on Industrial Engineering and Industrial Management, IEIM 2022 tenutosi a esp nel 2022 [10.1145/3524338.3524379].

An Iterative Matheuristic Algorithm for the B-Coloring Problem

Montemanni R.;
2022-01-01

Abstract

B-coloring is a problem in graph theory at the basis of several real applications and also used to improve solution methods for the classical coloring problem. Enhanced solutions for the classical coloring problem have in turn impacts on several other practical applications in scheduling, timetabling and telecommunications. Namely, given a graph G = (V, E), the b-coloring problem consists of maximizing the number of colors used while assigning a color to every vertex in V such that no pair of adjacent vertices receive the same color and every color has a representative, called a b-vertex. A vertex can be a b-vertex if it is adjacent to vertices colored with all the colors apart from the one assigned to it. In this paper we present a novel Iterative Matheuristic Algorithm based on considerations about the structure of promising solutions and a mathematical programming model. A vast section of computational experiments shows how the approach is able to find high quality solutions for commonly established datasets from the literature. In particular, the method we propose is able to improve the best known heuristic solution for 38 instances of the 137 considered. The optimality of the bounds previously known for another 5 instances has also been proved by running the approach we propose exhaustively.
3rd International Conference on Industrial Engineering and Industrial Management, IEIM 2022
esp
2022
265
270
Montemanni, R.; Smith, D. H.
An Iterative Matheuristic Algorithm for the B-Coloring Problem / Montemanni, R.; Smith, D. H.. - (2022), pp. 265-270. ((Intervento presentato al convegno 3rd International Conference on Industrial Engineering and Industrial Management, IEIM 2022 tenutosi a esp nel 2022 [10.1145/3524338.3524379].
File in questo prodotto:
File Dimensione Formato  
3524338.3524379.pdf

Open access

Tipologia: Versione pubblicata dall'editore
Dimensione 541.77 kB
Formato Adobe PDF
541.77 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1286084
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact