An analysis between the Welsh-Powell and DSatur algorithms for coloring of sparse graphs.
Saved in:
| Title: | An analysis between the Welsh-Powell and DSatur algorithms for coloring of sparse graphs. |
|---|---|
| Authors: | Kraleva, Radoslava1 rady_kraleva@swu.bg, Kralev, Velin1 velin_kralev@swu.bg, Katsarski, Toma1 t.katsarski@swu.bg |
| Source: | International Journal of Electrical & Computer Engineering (2088-8708). Aug2025, Vol. 15 Issue 4, p3867-3875. 9p. |
| Subjects: | Graph coloring, Sparse graphs, Algorithms, Time complexity |
| Abstract: | In this research an analysis between the Welsh-Powell and DSatur algorithms for the graph vertex coloring problem was presented. Both algorithms were implemented and analyzed as well. The method of the experiment was discussed and the 46 test graphs, which were divided into two sets, were presented. The results show that for sparse graphs with a smaller number of vertices and edges, both algorithms can be used for solving the problem. The results show that in 50% of the cases the Welsh-Powell algorithm found better solutions (23 in total). So, the DSatur algorithm found better solutions in only 19.6% of cases (9 in total). In the remaining 30.4% of cases, both algorithms found identical solutions. For graphs with a larger number of vertices, the usage of the Welsh-Powell algorithm is recommended as it finds better solutions. The execution time of the DSatur algorithm is greater than the execution time of the Welsh-Powell algorithm, reaching up to a minute for graphs with a larger number of vertices. For graphs with fewer vertices and edges, the execution times of both algorithms are shorter, but the time is still greater for the DSatur algorithm. [ABSTRACT FROM AUTHOR] |
| Copyright of International Journal of Electrical & Computer Engineering (2088-8708) is the property of Institute of Advanced Engineering & Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 187706902 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: An analysis between the Welsh-Powell and DSatur algorithms for coloring of sparse graphs. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Kraleva%2C+Radoslava%22">Kraleva, Radoslava</searchLink><relatesTo>1</relatesTo><i> rady_kraleva@swu.bg</i><br /><searchLink fieldCode="AR" term="%22Kralev%2C+Velin%22">Kralev, Velin</searchLink><relatesTo>1</relatesTo><i> velin_kralev@swu.bg</i><br /><searchLink fieldCode="AR" term="%22Katsarski%2C+Toma%22">Katsarski, Toma</searchLink><relatesTo>1</relatesTo><i> t.katsarski@swu.bg</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Electrical+%26+Computer+Engineering+%282088-8708%29%22">International Journal of Electrical & Computer Engineering (2088-8708)</searchLink>. Aug2025, Vol. 15 Issue 4, p3867-3875. 9p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Graph+coloring%22">Graph coloring</searchLink><br /><searchLink fieldCode="DE" term="%22Sparse+graphs%22">Sparse graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Time+complexity%22">Time complexity</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: In this research an analysis between the Welsh-Powell and DSatur algorithms for the graph vertex coloring problem was presented. Both algorithms were implemented and analyzed as well. The method of the experiment was discussed and the 46 test graphs, which were divided into two sets, were presented. The results show that for sparse graphs with a smaller number of vertices and edges, both algorithms can be used for solving the problem. The results show that in 50% of the cases the Welsh-Powell algorithm found better solutions (23 in total). So, the DSatur algorithm found better solutions in only 19.6% of cases (9 in total). In the remaining 30.4% of cases, both algorithms found identical solutions. For graphs with a larger number of vertices, the usage of the Welsh-Powell algorithm is recommended as it finds better solutions. The execution time of the DSatur algorithm is greater than the execution time of the Welsh-Powell algorithm, reaching up to a minute for graphs with a larger number of vertices. For graphs with fewer vertices and edges, the execution times of both algorithms are shorter, but the time is still greater for the DSatur algorithm. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of International Journal of Electrical & Computer Engineering (2088-8708) is the property of Institute of Advanced Engineering & Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=187706902 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.11591/ijece.v15i4.pp3867-3875 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 9 StartPage: 3867 Subjects: – SubjectFull: Graph coloring Type: general – SubjectFull: Sparse graphs Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Time complexity Type: general Titles: – TitleFull: An analysis between the Welsh-Powell and DSatur algorithms for coloring of sparse graphs. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Kraleva, Radoslava – PersonEntity: Name: NameFull: Kralev, Velin – PersonEntity: Name: NameFull: Katsarski, Toma IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 08 Text: Aug2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 20888708 Numbering: – Type: volume Value: 15 – Type: issue Value: 4 Titles: – TitleFull: International Journal of Electrical & Computer Engineering (2088-8708) Type: main |
| ResultId | 1 |
