| 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 | 2019-09-02 11:25 Speeding-up of Construction Algorithms for the Graph Coloring Problem Kazuho Kanahara, Kengo Katayama (OUS), Etsuji Tomita (UEC), Takeshi Okano, Takahumi Miyake, Noritaka Nishihara (OUS)  COMP2019-11 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | DSATUR and RLF are well known as typical solution construction algorithms for the graph coloring problem, GCP, where GCP is one of the combinatorial optimization problems that have important practical applications. It is necessary to update the vertex degree in the subgraph 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. In this paper, we propose a subgraph degree updating method to improve this issue. Experimental results show that the proposed method is faster than the conventional method and LazyRLF, especially for graphs with high edge density. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | combinatorial optimization / graph coloring problem / construction algorithms / / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 119, no. 191, COMP2019-11, pp. 7-14, Sept. 2019. | |
| Paper # | COMP2019-11 | |
| Date of Issue | 2019-08-26 (COMP) | |
| ISSN | 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 | COMP2019-11 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2019-09-02 - 2019-09-02 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Tsushima Campus, Okayama University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2019-09-COMP |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Speeding-up of Construction Algorithms for the Graph Coloring Problem |
| Sub Title (in English) | |
| Keyword(1) | combinatorial optimization |
| Keyword(2) | graph coloring problem |
| Keyword(3) | construction algorithms |
| Keyword(4) | |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Kazuho Kanahara |
| 1st Author's Affiliation | Okayama University of Science (OUS) |
| 2nd Author's Name | Kengo Katayama |
| 2nd Author's Affiliation | Okayama University of Science (OUS) |
| 3rd Author's Name | Etsuji Tomita |
| 3rd Author's Affiliation | The University of Electro-Communications (UEC) |
| 4th Author's Name | Takeshi Okano |
| 4th Author's Affiliation | Okayama University of Science (OUS) |
| 5th Author's Name | Takahumi Miyake |
| 5th Author's Affiliation | Okayama University of Science (OUS) |
| 6th Author's Name | Noritaka Nishihara |
| 6th Author's Affiliation | Okayama University of Science (OUS) |
| 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 | 2019-09-02 11:25:00 |
| Presentation Time | 35 minutes |
| Registration for | COMP |
| Paper # | COMP2019-11 |
| Volume (vol) | vol.119 |
| Number (no) | no.191 |
| Page | pp.7-14 |
| #Pages | 8 |
| Date of Issue | 2019-08-26 (COMP) |
[Return to Top Page]