Show simple item record

AuthorJaam, Jihad M.
AuthorHasnah, Ahmad M.
Available date2024-03-20T01:55:10Z
Publication Date2003
Publication NameArab Gulf Journal of Scientific Research
ResourceScopus
ISSN19859899
URIhttp://hdl.handle.net/10576/53287
AbstractIn 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.
Languageen
PublisherArabian Gulf University
SubjectAlgorithm
DSATUR
Graph coloring
Lipartite graphs
TitleImprovement of the DSATUR algorithm for graph coloring
TypeArticle
Pagination90-94
Issue Number2
Volume Number21
dc.accessType Abstract Only


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record