IEICE TRANSACTIONS on Fundamentals
Speeding-Up Construction Algorithms for the Graph Coloring Problem
Summary :
The Graph Coloring Problem (GCP) is a fundamental combinatorial optimization problem that has many practical applications. Degree of SATURation (DSATUR) and Recursive Largest First (RLF) are well known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph induced by uncolored vertices when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. The purposes of this paper are to propose a degree updating method called Adaptive Degree Updating (ADU for short) that improves the issue, and to evaluate the effectiveness of ADU for DSATUR and RLF on DIMACS benchmark graphs as well as random graphs having a wide range of sizes and densities. Experimental results show that the construction algorithms with ADU are faster than the conventional algorithms for many graphs and that the ADU method yields significant speed-ups relative to the conventional algorithms, especially in the case of large graphs with higher edge density.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E105-A No.9 pp.1241-1251
- Publication Date
- 2022/09/01
- Publicized
- 2022/03/18
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2021DMP0011
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Numerical Analysis and Optimization, Algorithms and Data Structures, Graphs and Networks
Authors
Kazuho KANAHARA
Okayama University of Science
Kengo KATAYAMA
Okayama University of Science
Etsuji TOMITA
The University of Electro-Communications
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuho KANAHARA, Kengo KATAYAMA, Etsuji TOMITA, "Speeding-Up Construction Algorithms for the Graph Coloring Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 9, pp. 1241-1251, September 2022, doi: 10.1587/transfun.2021DMP0011.
Abstract: The Graph Coloring Problem (GCP) is a fundamental combinatorial optimization problem that has many practical applications. Degree of SATURation (DSATUR) and Recursive Largest First (RLF) are well known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph induced by uncolored vertices when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. The purposes of this paper are to propose a degree updating method called Adaptive Degree Updating (ADU for short) that improves the issue, and to evaluate the effectiveness of ADU for DSATUR and RLF on DIMACS benchmark graphs as well as random graphs having a wide range of sizes and densities. Experimental results show that the construction algorithms with ADU are faster than the conventional algorithms for many graphs and that the ADU method yields significant speed-ups relative to the conventional algorithms, especially in the case of large graphs with higher edge density.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021DMP0011/_p
Copy
@ARTICLE{e105-a_9_1241,
author={Kazuho KANAHARA, Kengo KATAYAMA, Etsuji TOMITA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Speeding-Up Construction Algorithms for the Graph Coloring Problem},
year={2022},
volume={E105-A},
number={9},
pages={1241-1251},
abstract={The Graph Coloring Problem (GCP) is a fundamental combinatorial optimization problem that has many practical applications. Degree of SATURation (DSATUR) and Recursive Largest First (RLF) are well known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph induced by uncolored vertices when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. The purposes of this paper are to propose a degree updating method called Adaptive Degree Updating (ADU for short) that improves the issue, and to evaluate the effectiveness of ADU for DSATUR and RLF on DIMACS benchmark graphs as well as random graphs having a wide range of sizes and densities. Experimental results show that the construction algorithms with ADU are faster than the conventional algorithms for many graphs and that the ADU method yields significant speed-ups relative to the conventional algorithms, especially in the case of large graphs with higher edge density.},
keywords={},
doi={10.1587/transfun.2021DMP0011},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Speeding-Up Construction Algorithms for the Graph Coloring Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1241
EP - 1251
AU - Kazuho KANAHARA
AU - Kengo KATAYAMA
AU - Etsuji TOMITA
PY - 2022
DO - 10.1587/transfun.2021DMP0011
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2022
AB - The Graph Coloring Problem (GCP) is a fundamental combinatorial optimization problem that has many practical applications. Degree of SATURation (DSATUR) and Recursive Largest First (RLF) are well known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph induced by uncolored vertices when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. The purposes of this paper are to propose a degree updating method called Adaptive Degree Updating (ADU for short) that improves the issue, and to evaluate the effectiveness of ADU for DSATUR and RLF on DIMACS benchmark graphs as well as random graphs having a wide range of sizes and densities. Experimental results show that the construction algorithms with ADU are faster than the conventional algorithms for many graphs and that the ADU method yields significant speed-ups relative to the conventional algorithms, especially in the case of large graphs with higher edge density.
ER -
English
