Abstract
We present an exact and efficient branch-and-bound algorithm for finding a maximum clique in an arbitrary graph. The algorithm is not specialized for any particular kind of graph. It employs approximate coloring and appropriate sorting of vertices to get an upper bound on the size of a maximum clique. We demonstrate by computational experiments on random graphs with up to 15,000 vertices and on DIMACS benchmark graphs that our algorithm remarkably outperforms other existing algorithms in general. It has been successfully applied to interesting problems in bioinformatics, image processing, the design of quantum circuits, and the design of DNA and RNA sequences for bio-molecular computation.
This work is partially supported by Grant-in-Aid for Scientific Research No.13680435 from MESSC of Japan and Research Fund of the University of Electro-Communications. It is also given a grant by Funai Foundation for Information Technology.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Balas and C.S. Yu: “Finding a maximum clique in an arbitrary graph,” SIAM J. Comput. 15, pp.1054–1068 (1986).
D. Bahadur K.C., T. Akutsu, E. Tomita, T. Seki, and A. Fujiyama: “Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms,” Genome Informatics 13, pp.143–152 (2002).
E. Balas, S. Ceria, G. Cornuéjols, and G. Pataki: “Polyhedral methods for the maximum clique problem,” pp.11–28 in [9] (1996).
I.M. Bomze, M. Budinich, P.M. Pardalos, and M. Pelillo: “The Maximum Clique Problem.” In: D.-Z. Du and P.M. Pardalos (Eds.), Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, pp.1–74 (1999).
J.-M. Bourjolly, P. Gill, G. Laporte, and H. Mercure: “An exact quadratic 0–1 algorithm for the stable set problem,” pp.53–73 in [9] (1996).
R. Carraghan and P.M. Pardalos: “An exact algorithm for the maximum clique problem,” Oper. Res. Lett. 9, pp.375–382 (1990).
T. Fujii and E. Tomita: “On efficient algorithms for finding a maximum clique,” Technical Report of IECE (in Japanese), AL81-113, pp.25–34 (1982).
K. Hotta, E. Tomita, T. Seki, and H. Takahashi: “Object detection method based on maximum cliques,” Technical Report of IPSJ (in Japanese), 2002-MPS-42, pp.49–56 (2002).
D. S. Johnson and M. A. Trick, (Eds.): “Cliques, Coloring, and Satisfiability,” DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.26, American Mathematical Society (1996).
S. Kobayashi, T. Kondo, K. Okuda, and E. Tomita: “Extracting globally structure free sequences by local structure freeness,” Technical Report CS 03-01, Dept. of Computer Science, Univ. of Electro-Communications (2003).
Y. Nakui, T. Nishino, E. Tomita, and T. Nakamura: “On the minimization of the quantum circuit depth based on a maximum clique with maximum vertex weight,” Technical Report of Winter LA Symposium 2002, pp.9.1–9.7 (2003).
P.R.J. Östergård: “A fast algorithm for the maximum clique problem,” Discrete Appl. Math. 120, pp.197–207 (2002).
P.M. Pardalos and J. Xue: “The maximum clique problem,” J. Global Optimization 4, pp. 301–328 (1994).
T. Seki and E. Tomita: “Efficient branch-and-bound algorithms for finding a maximum clique,” Technical Report of IEICE (in Japanese), COMP 2001-50, pp.101–108 (2001).
E.C. Sewell: “A branch and bound algorithm for the stability number of a sparse graph,” INFORMS J. Comput. 10, pp.438–447 (1998).
E. Tomita, Y. Kohata, and H. Takahashi: “A simple algorithm for finding a maximum clique,” Techical Report UEC-TR-C5, Dept. of Communications and Systems Engineering, Univ. of Electro communications (1988).
D. R. Wood: “An algorithm for finding a maximum clique in a graph,” Oper. Res. Lett. 21, pp.211–217 (1997).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tomita, E., Seki, T. (2003). An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds) Discrete Mathematics and Theoretical Computer Science. DMTCS 2003. Lecture Notes in Computer Science, vol 2731. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45066-1_22
Download citation
DOI: https://doi.org/10.1007/3-540-45066-1_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40505-4
Online ISBN: 978-3-540-45066-5
eBook Packages: Springer Book Archive