| Presentation | 2009-01-30 VNS-based Enhancing of a Distributed Branch-and-Bound Algorithm ParaBSC for the Graph Coloring Problem Yukihiro DOGO, Satoshi TAOKA, Toshimasa WATANABE, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Given an undirected graph G, a coloring is an assignment of colors to vertices of G such that any pair of adjacent vertices (they are linked by an edge) have different colors. The graph coloring problem is a problem of obtaining the smallest number of colors needed to color all vertices of G as well as its coloring (called "an exact coloring"), and it is known to be NP-hard. So a distributed branch-and-bound algorithm ParaBSC has been proposed in order to obtain an exact coloring rapidly. Even if it is used, its computing time is likely to increase exponentially. In this paper, ParaBSC is going to be enhanced by utilizing a heuristic coloring procedure VNS_TO, and its capability is evaluated through computing experiment. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Graph coloring problems / chromatic numbers / variable neighborhood search / approximation algorithms / branch-and-bound algorithms |
| Paper # | CST2008-52 |
| Date of Issue |
| Conference Information | |
| Committee | CST |
|---|---|
| Conference Date | 2009/1/22(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Concurrent System Technology (CST) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | VNS-based Enhancing of a Distributed Branch-and-Bound Algorithm ParaBSC for the Graph Coloring Problem |
| Sub Title (in English) | |
| Keyword(1) | Graph coloring problems |
| Keyword(2) | chromatic numbers |
| Keyword(3) | variable neighborhood search |
| Keyword(4) | approximation algorithms |
| Keyword(5) | branch-and-bound algorithms |
| 1st Author's Name | Yukihiro DOGO |
| 1st Author's Affiliation | Faculty of Engineering, Hiroshima University() |
| 2nd Author's Name | Satoshi TAOKA |
| 2nd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
| 3rd Author's Name | Toshimasa WATANABE |
| 3rd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
| Date | 2009-01-30 |
| Paper # | CST2008-52 |
| Volume (vol) | vol.108 |
| Number (no) | 415 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |