Abstract: A clique is a subgraph in which all pairs of vertices are mutually adjacent. A maximum clique is a clique of the maximum size. Thus, a maximum clique stands for a maximum collection of objects which are mutually related in some specified criterion.
The so called maximum clique problem, or the complementary problem, the maximum independent set problem, is one of the original 21 problems shown to be NP-complete by R. Karp. Therefore, it is strongly believed that the maximum clique problem is not solvable easily, i.e., it is not solvable in polynomial-time. Nevertheless, much work has been done on this problem, experimentally and theoretically. It attracts much attention especially recently since it has found many practical applications.
In this lecture, we are concerned with recent progress of efficient algorithms for finding a maximum clique. We focus on branch-and-bound algorithms in which appropriate bounding condition is most crucial. The step-by-step improvements on the bounding condition and their effectiveness are presented. Some algorithms for generating all maximal cliques are also shown. We give evaluations on these algorithms not only experimentally but also theoretically. We also give a natural condition in which the maximum clique problem can be proved to be polynomial-time solvable.
In addition, we address successful applications of these algorithms to bioinformatics, image processing, data mining, and others.

Brief Biography of the Speaker:
Etsuji Tomita received his B. Eng. and Dr. Eng. degrees in Electronics Engineering from Tokyo Institute of Technology, Japan, in 1966 and 1971, respectively. Then he was with the faculties of Tokyo Institute of Technology, and was appointed Associate Professor and subsequently Professor at the University of Electro-Communications, Japan. Since 2008, he has been Professor Emeritus at the University of Electro-Communications and Professor at the Research and Development Initiative of Chuo University. He also teaches at Hokkaido University as a part-time lecturer. He served as the Head of the department of Information and Communication Engineering, and the Head of the Advanced Algorithms Research Laboratory at UEC.
His research interests include design and analysis of computer algorithms, combinatorial optimization and its application to practical problems, algorithmic learning theory, and theory of automata and formal languages.
His academic contributions include Editor of IEICE (Institute of Electronics, Information and Communication Engineers) and Editor-in-Chief of IPSJ (Information processing Society of Japan), Local Arrangement Chair of ALT (Algorithmic Learning Theory), Chair of SIG Mathematical Modeling and Problem Solving of IPSJ, Program Committee Chair of ALT 2005, and he served as a Guest Editor of Theoretical Computer Science, Conference Chair of ICGI (International Colloquium on Grammatical Inference) 2006, Director of IPSJ, Chair of Computer Science Domain of IPSJ, and Councilor of JSAI (The Japanese Society for Artificial Intelligence). He is presently a member of Steering Committee of ICGI.
He was given the Yonezawa Award of IECE, the Funai Information Technology Prize, and the Contribution Award of SIG MPS of IPSJ, and is presently a Fellow of IEICE and IPSJ.
He is a co-author of two papers that were given Yamashita Research Award of IPSJ, and of a paper that was given Encouraging Award of Computer Science Domain of IPSJ.