Numerical experiences with graph coloring algorithms (Q1070239)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Numerical experiences with graph coloring algorithms |
scientific article; zbMATH DE number 3935076
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Numerical experiences with graph coloring algorithms |
scientific article; zbMATH DE number 3935076 |
Statements
Numerical experiences with graph coloring algorithms (English)
0 references
1986
0 references
Sequential vertex colouring algorithms are compared on 3000 random graphs having \(n=25\) (25) 300 vertices and edge density \(p=0.1\), 0.25, 0.50, 0.75, 0.90. Fixed-order and dynamic-order approaches using the random/largest-first/smallest-last heuristic for choosing vertices and the minimum-index/lookahead rule for choosing colours are discussed. Detailed measurements are listed. The dynamic largest-first lookahead algorithm seems to be superior in most cases.
0 references
computational analysis
0 references
Sequential vertex colouring algorithms
0 references
random graphs
0 references
0 references
0.8699849247932434
0 references
