アブストラクト
| Date | 2:00pm Feb 07, 2020 |
| 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] Etsuji Tomita, Sora Matsuzaki, Atsuki Nagao, Hiro Ito, Mitsuo Wakatsuki, " A much faster branch-and-bound algorithm for finding a maximum clique with computational experiments, " Journal of Information Processing, 25, pp.667-677 (2017) |