| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2008-01-31 13:25 Enhancing Algorithms for the Graph Coloring Problem Shinji Okada, Satoshi Taoka, Toshimasa Watanabe (Hiroshima Univ.)  CAS2007-85 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | Coloring a given graph $G=(V,E)$ is to assign each vertex $v$ of $V$ a color $c(v)$ such that $c(u)$ is different from $c(u')$ for any edge $(u,u')$ of $E$. For any positive integer k, k-coloring means coloring a given graph with at most k colors. The minimum number $\chi(G)$ of colors required in coloring $G$ is called the chromatic number of $G$ . The graph coloring problem is the problem of determining $\chi(G)$ and $c(v)$ of each vertex $v$ of $V$ for any given graph $G=(V,E)$, and it is known to be NP-hard. This report tries to enhance approximation algorithms for the problem by improving an existing procedure VNS (Variable Neighborhood Search), and show evaluation through computing experiment. As an application of the results, it is shown that CPU time of a branch-and-bound algorithm is reduced by using the number of colors given by any enhanced algorithm as an upper bound of $\chi(G)$. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | Graph coloring problems / chromatic numbers / variable neighborhood search / approximation algorithms / branch-and-bound algorithms / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 107, no. 475, CAS2007-85, pp. 7-12, Jan. 2008. | |
| Paper # | CAS2007-85 | |
| Date of Issue | 2008-01-24 (CAS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | CAS2007-85 |
|
| Conference Information | |
| Committee | CAS |
| Conference Date | 2008-01-31 - 2008-02-01 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | CAS |
| Conference Code | 2008-01-CAS |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Enhancing Algorithms 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 |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Shinji Okada |
| 1st Author's Affiliation | Hiroshima University (Hiroshima Univ.) |
| 2nd Author's Name | Satoshi Taoka |
| 2nd Author's Affiliation | Hiroshima University (Hiroshima Univ.) |
| 3rd Author's Name | Toshimasa Watanabe |
| 3rd Author's Affiliation | Hiroshima University (Hiroshima Univ.) |
| 4th Author's Name | |
| 4th Author's Affiliation | () |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| 7th Author's Name | |
| 7th Author's Affiliation | () |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2008-01-31 13:25:00 |
| Presentation Time | 25 minutes |
| Registration for | CAS |
| Paper # | CAS2007-85 |
| Volume (vol) | vol.107 |
| Number (no) | no.475 |
| Page | pp.7-12 |
| #Pages | 6 |
| Date of Issue | 2008-01-24 (CAS) |
[Return to Top Page]