当研究室で取り組んでいる研究に関する論文・講演などの情報（一部抜粋）です。
Here is a selection of our published papers on the research we’ve been working on in our laboratory.
Our Selected Papers and Keywords
2022
Kazuho Kanahara, Kengo Katayama, Etsuji Tomita
Speeding-up construction algorithms for the graph coloring problem Journal Article
In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E105.A, no. 9, pp. 1241-1251, 2022, ISSN: 1745-1337.
Abstract | BibTeX | タグ: Combinatorial optimization, Construction algorithm, DSATUR, Graph coloring problem, RLF | Links:
@article{KANAHARA-IEICE-2022,
title = {Speeding-up construction algorithms for the graph coloring problem},
author = {Kazuho Kanahara and Kengo Katayama and Etsuji Tomita},
doi = {10.1587/transfun.2021DMP0011},
issn = {1745-1337},
year = {2022},
date = {2022-09-01},
urldate = {2022-09-01},
journal = {IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences},
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 = {Combinatorial optimization, Construction algorithm, DSATUR, Graph coloring problem, RLF},
pubstate = {published},
tppubtype = {article}
}
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.