It is a common practice in exact enumerative algorithms for graph colouring to find a clique of maximum cardinality and to fix the colours of this subgraph before proceeding with implicit enumeration on the remainder of the graph. The goal of this experimental study is to analyse the effects on the enumeration process of some implementation issues related to the choice of such a clique. This paper is provided with experiments on random graphs and benchmarks.

Evaluating the Effects of the Clique Selection in Exact Graph Coloring Algorithms / M., Caramia; P., Dellolmo; I. N., Exact Graph Coloring Algorithms Evaluating The Effects Of The Clique Selection; International Journal O. F., Operational Research; Dell'Olmo, Paolo. - In: INTERNATIONAL JOURNAL OF OPERATIONAL RESEARCH. - ISSN 1745-7645. - STAMPA. - 11:2(2011), pp. 179-192. [10.1504/ijor.2011.040696]

Evaluating the Effects of the Clique Selection in Exact Graph Coloring Algorithms

DELL'OLMO, Paolo
2011

Abstract

It is a common practice in exact enumerative algorithms for graph colouring to find a clique of maximum cardinality and to fix the colours of this subgraph before proceeding with implicit enumeration on the remainder of the graph. The goal of this experimental study is to analyse the effects on the enumeration process of some implementation issues related to the choice of such a clique. This paper is provided with experiments on random graphs and benchmarks.
2011
clique; implicit enumeration; graph coloring
01 Pubblicazione su rivista::01a Articolo in rivista
Evaluating the Effects of the Clique Selection in Exact Graph Coloring Algorithms / M., Caramia; P., Dellolmo; I. N., Exact Graph Coloring Algorithms Evaluating The Effects Of The Clique Selection; International Journal O. F., Operational Research; Dell'Olmo, Paolo. - In: INTERNATIONAL JOURNAL OF OPERATIONAL RESEARCH. - ISSN 1745-7645. - STAMPA. - 11:2(2011), pp. 179-192. [10.1504/ijor.2011.040696]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/47777
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact