The search functionality is under construction.

The search functionality is under construction.

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

Kazuho KANAHARA

Okayama University of Science

Kengo KATAYAMA

Okayama University of Science

Etsuji TOMITA

The University of Electro-Communications

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.

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 -