Evaluating the effects of the clique selection in exact graph colouring algorithms (Q659453)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5999219
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Evaluating the effects of the clique selection in exact graph colouring algorithms |
scientific article; zbMATH DE number 5999219 |
Statements
Evaluating the effects of the clique selection in exact graph colouring algorithms (English)
0 references
18 January 2012
0 references
Summary: 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.
0 references
clique selection
0 references
implicit enumeration
0 references
vertex colouring
0 references
0.7910874485969543
0 references
0.7910537123680115
0 references
0.7909275889396667
0 references
0.7856345772743225
0 references
