Improvement of the DSATUR algorithm for graph coloring
Author | Jaam, Jihad M. |
Author | Hasnah, Ahmad M. |
Available date | 2024-03-20T01:55:10Z |
Publication Date | 2003 |
Publication Name | Arab Gulf Journal of Scientific Research |
Resource | Scopus |
ISSN | 19859899 |
Abstract | In this paper we discuss the deterministic Brelaz's DSATUR algorithm for graph coloring. We propose a simple modification that improves the performance of the algorithm. This modification consists of assigning the color that saturates the least number of uncolored vertices, to the selected vertex. Thus, we obtain valid k-colorings better than those obtained with DSATUR without modification. We show also that the DSATUR algorithm is optimal, for a given example, and for the bipartite graphs. |
Language | en |
Publisher | Arabian Gulf University |
Subject | Algorithm DSATUR Graph coloring Lipartite graphs |
Type | Article |
Pagination | 90-94 |
Issue Number | 2 |
Volume Number | 21 |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
-
Computer Science & Engineering [2284 items ]