Name
Abstract | ||
|---|---|---|
In many computer vision and pattern recognition applications using graph-based representations, it is of great interest to be able to extract the k largest cliques in a graph. However, most methods are geared either towards extracting a single clique of maximum size, or enumerating all cliques, without following any particular order. In this paper, we present a novel approach for partial clique enumeration, which is the problem of extracting the k largest cliques of a graph. Our approach is based on a continuous formulation of the clique problem developed in the 1960s by Motzkin and Straus, and is able to avoid extracting the same clique multiple times. This is done by casting the problem into a game-theoretic framework, where stable strategies are in correspondence with maximal cliques, and by iteratively rendering the extracted solutions unstable. The approach has been tested on the maximum clique problem and compared against several state-of-the-art algorithms both on random as well as DIMACS benchmark graphs. Further, we applied our enumerative heuristic to the matching of shapes using the shock-graph representation. The results confirm the effectiveness of the approach. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.imavis.2008.10.003 | Image Vision Comput. |
Keywords | Field | DocType |
evolutionary stable strategy,partial clique enumeration,maximal clique enumeration,maximum clique problem,novel approach,dimacs benchmark graph,k largest clique,evolutionary game theory,single clique,clique multiple time,maximal clique enumeration maximum clique problem evolutionary game theory evolutionary stable strategy,maximal clique,maximum size,game-theoretic approach,clique problem,pattern recognition | Combinatorics,Clique,Clique graph,K-tree,Clique-sum,Treewidth,Mathematics,Clique (graph theory),Clique problem,Split graph | Journal |
Volume | Issue | ISSN |
27 | 7 | Image and Vision Computing |
Citations | PageRank | References |
17 | 0.67 | 33 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Rota Bulò | 1 | 564 | 33.69 |
| Andrea Torsello | 2 | 957 | 64.08 |
| Marcello Pelillo | 3 | 1888 | 150.33 |