Date 
2:00pm Feb 07, 2020 
Speaker 
Etsuji Tomita
Professor Emeritus,
The Advanced Algorithms Research Laboratory, The University of ElectroCommunications, 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 depthfirst branchandbound
algorithms for finding a maximum clique that employ powerful upper
bounds of the size of a maximum clique. Second, we show a depthfirst
algorithm for enumerating all maximal cliques, whose time complexity can
be proved to be optimal in the worstcase. Finally, some applications of
the previous algorithms to practical problems will be presented.
References
[1] Etsuji Tomita, " Clique enumeration," in MingYang Kao (Ed.),
" Encyclopedia of Algorithms, 2nd Edition" Springer, pp.313327 (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.315 (2017)
[3] Etsuji Tomita, Sora Matsuzaki, Atsuki Nagao, Hiro Ito, Mitsuo
Wakatsuki, " A much faster branchandbound algorithm for finding a
maximum clique with computational experiments, " Journal of Information
Processing, 25, pp.667677 (2017) 
