Abstract
Many computer vision and patter recognition problems are intimately related to the maximum clique problem. Due to the intractability of this problem, besides the development of heuristics, a research direction consists in trying to find good bounds on the clique number of graphs. This paper introduces a new spectral upper bound on the clique number of graphs, which is obtained by exploiting an invariance of a continuous characterization of the clique number of graphs introduced by Motzkin and Straus. Experimental results on random graphs show the superiority of our bounds over the standard literature.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barrow, H., Burstall, R.M.: Subgraph isomorphism, matching relational structures and maximal cliques. Information Processing Letters 4(4), 83–84 (1976)
Chin, R.T., Dyer, C.R.: Model-based recognition in robot vision. Comput. Surveys 18(1), 67–108 (1986)
Pelillo, M., Siddiqi, K., Zucker, S.W.: Matching hierarchical structures using association graphs. IEEE Trans. Pattern Anal. Machine Intell. 21(11), 1105–1120 (1999)
Suetens, P., Fua, P., Hanson, A.J.: Computational strategies for object recognition. Comput. Surveys 24(1), 5–61 (1992)
Ambler, A.P., Barrow, H.G., Brown, C.M., Burstall, R.M., Popplestone, R.J.: A versatile computer-controlled assembly. In: Int. Joint Conf. on Artif. Intell., pp. 298–307 (1973)
Bolles, R.C., Cain, R.A.: Recognizing and locating partially visible objects: the local-feature-focus method. Int. J. Robotics Res. 1(n), 57–82 (1982)
Horaud, R., Skordas, T.: Stereo correspondence through feature grouping and maximal cliques. IEEE Trans. Pattern Anal. Machine Intell. 11(11), 1168–1180 (1989)
Ogawa, H.: Labeled point pattern matching by delaunay triangulation and maximal cliques. Pattern Recogn. 19(1), 35–40 (1986)
Radig, B.: Image sequence analysis using relational structures. Pattern Recogn. 17(1), 161–167 (1984)
Augustson, J.G., Minker, J.: An analysis of some graph theoretical cluster techniques. J. ACM 17(4), 571–588 (1970)
Jain, A.K., Dubes, R.C.: Algorithms for data clustering. Prentice-Hall, Englewood Cliffs (1988)
Pavan, M., Pelillo, M.: Dominant sets and pairwise clustering. IEEE Trans. Pattern Anal. Machine Intell. 29(1), 167–172 (2007)
Dmitry, D., Ari, R.: Efficient unsupervised discovery of word categories using symmetric patterns and high frequency words. In: 21st Int. Conf. on Computational Linguistics and 44th Annual Meeting of the ACL, Association for Computational Linguistics, pp. 297–304 (2006)
Nina, M., Dana, R., Ram, S.: A new conceptual clustering framework. Machine Learning 56, 115–151 (2004)
Hammersley, J., Clifford, P.: Markov fields on finite graphs and lattices (1971)
Hastad, J.: Clique is hard to approximate within n 1 − ε. In: Ann. Symp. Found. Comput. Sci., vol. 37, pp. 627–636 (1996)
Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Handbook of Combinatorial Optimization, vol. 1, pp. 1–74. Kluwer Academic Publishers, Boston (1999)
Budinich, M.: Exact bounds on the order of the maximum clique of a graph. Discr. Appl. Math. 127, 535–543 (2003)
Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Canad. J. Math. 17, 533–540 (1965)
Pelillo, M.: Replicator equations, maximal cliques, and graph isomorphism. Neural Computation 11(8), 1933–1955 (1999)
Schellewald, C.: A bound for non-subgraph isomorphism. In: Escolano, F., Vento, M. (eds.) GbRPR. LNCS, vol. 4538, pp. 71–80. Springer, Heidelberg (2007)
Lu, M., Liu, H., Tian, F.: Laplacian spectral bounds for clique and independence numbers of graphs. J. Combin. Theory Series B 97(5), 726–732 (2007)
Wilf, H.S.: The eigenvalues of a graph and its chromatic number. J. London Math. Soc. 42, 330–332 (1967)
Amin, A.T., Hakimi, S.L.: Upper bounds of the order of a clique of a graph. SIAM J. on Appl. Math. 22(4), 569–573 (1972)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bulò, S.R., Pelillo, M. (2010). A New Spectral Bound on the Clique Number of Graphs. In: Hancock, E.R., Wilson, R.C., Windeatt, T., Ulusoy, I., Escolano, F. (eds) Structural, Syntactic, and Statistical Pattern Recognition. SSPR /SPR 2010. Lecture Notes in Computer Science, vol 6218. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14980-1_67
Download citation
DOI: https://doi.org/10.1007/978-3-642-14980-1_67
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14979-5
Online ISBN: 978-3-642-14980-1
eBook Packages: Computer ScienceComputer Science (R0)