| 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 | 2021-03-08 15:45 A further improved MCT algorithm for finding a maximum clique Jiro Yanagisawa, Etsuji Tomita (UEC), Kengo Katayama, Kanahara Kazuho (OUS), Takahisa Toda, Hiro Ito, Mitsuo Wakatsuki, Tetsuro Nishino (UEC)  COMP2020-35 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | We improve further the MCT algorithm for finding a maximum clique （FAW 2016, LNCS 9711, pp.215-226, 2016). First, we employ a new efficient approximation algorithm for finding a maximum clique. Second, we change the threshold to enable the appropriate disposal of search trees depending on the scale. Third, we employ a branch-and-bound technique that has already been shown effective by other algorithms. It is shown that a new algorithm is much faster than MCT by extensive computational experiments. In addition, it is shown that the new algorithm is faster than the up-to-date IncMC2 algorithm （INFORMS J. Computing, 30, pp.137-153, 2018） for many problems. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | maximum clique / depth-first search / approximation algorithm / graph theory / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 120, no. 426, COMP2020-35, pp. 38-45, March 2021. | |
| Paper # | COMP2020-35 | |
| Date of Issue | 2021-03-01 (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 | COMP2020-35 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2021-03-08 - 2021-03-08 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2021-03-COMP |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A further improved MCT algorithm for finding a maximum clique |
| Sub Title (in English) | |
| Keyword(1) | maximum clique |
| Keyword(2) | depth-first search |
| Keyword(3) | approximation algorithm |
| Keyword(4) | graph theory |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Jiro Yanagisawa |
| 1st Author's Affiliation | The University of Electro-Communications (UEC) |
| 2nd Author's Name | Etsuji Tomita |
| 2nd Author's Affiliation | The University of Electro-Communications (UEC) |
| 3rd Author's Name | Kengo Katayama |
| 3rd Author's Affiliation | Okayama University of Science (OUS) |
| 4th Author's Name | Kanahara Kazuho |
| 4th Author's Affiliation | Okayama University of Science (OUS) |
| 5th Author's Name | Takahisa Toda |
| 5th Author's Affiliation | The University of Electro-Communications (UEC) |
| 6th Author's Name | Hiro Ito |
| 6th Author's Affiliation | The University of Electro-Communications (UEC) |
| 7th Author's Name | Mitsuo Wakatsuki |
| 7th Author's Affiliation | The University of Electro-Communications (UEC) |
| 8th Author's Name | Tetsuro Nishino |
| 8th Author's Affiliation | The University of Electro-Communications (UEC) |
| 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 | 2021-03-08 15:45:00 |
| Presentation Time | 30 minutes |
| Registration for | COMP |
| Paper # | COMP2020-35 |
| Volume (vol) | vol.120 |
| Number (no) | no.426 |
| Page | pp.38-45 |
| #Pages | 8 |
| Date of Issue | 2021-03-01 (COMP) |
[Return to Top Page]