ゲノム情報科学研究教育機構  アブストラクト
Date Apr 16, 2019
Speaker Etsuji Tomita,
Professor Emeritus
The Advanced Algorithms Research Laboratory, The University of Electro-Communications, Japan
Title The Maximum Clique Problem and Its Applications
Abstract The maximum clique problem is a typical NP complete problem and is very important in theory. In addition, it has many practical applications in bioinformatics, pattern recognition and image processing, coding theory, data mining, design of wireless networks and others. First, we should like to present some depth-first branch-and-bound algorithms for finding a maximum clique that employ powerful upper bounds of the size of a maximum clique. Second, we show a depth-first algorithm for enumerating all maximal cliques, whose time complexity can be proved to be optimal in the worst-case. Finally, some applications of the previous algorithms to practical problems will be presented.

References:
  1. Etsuji Tomita, " Clique enumeration," in Ming-Yang Kao (Ed.), " Encyclopedia of Algorithms, 2nd Edition" Springer, pp.313-327 (2016)
  2. Etsuji Tomita, " Efficient algorithms for finding maximum and maximal cliques and their applications – Keynote – ," WALCOM 2017, Hsinchu, Taiwan, Lecture Notes in Computer Science 10167, Springer, pp.3-15 (2017)
  3. Sora Matsuzaki, Etsuji Tomita, Atsuki Nagao, Hiro Ito, Mitsuo Wakatsuki, Tetsuro Nishino, " An improved MCT algorithm for finding a maximum clique (in Japanese), " IPSJ SIG Technical Report, 2018-MPS-120，21, pp.1-6 (2018)
「セミナー」に戻る      
 ホーム