Paper Info
Title
A new spectral bound on the clique number of graphs
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.
Year
DOI
Venue
2010
10.1007/978-3-642-14980-1_67
SSPR/SPR
Keywords
Field
DocType
random graph,maximum clique problem,research direction,good bound,clique number,computer vision,new spectral,patter recognition problem,standard literature,continuous characterization,upper bound
Discrete mathematics,Combinatorics,Indifference graph,Clique graph,Chordal graph,Clique-sum,Treewidth,Clique (graph theory),Mathematics,Clique problem,Split graph
Conference
Volume
ISSN
ISBN
6218
0302-9743
3-642-14979-0
Citations 
PageRank 
References 
0
0.34
17
Authors
2
Name
Order
Citations
PageRank
Samuel Rota Bulò156433.69
Marcello Pelillo21888150.33