Name
Abstract | ||
|---|---|---|
The problem of finding a maximum clique in a graph is prototypical for many clustering and similarity problems; however, in many real-world scenarios, the classical problem of finding a complete subgraph needs to be relaxed to finding an almost complete subgraph, a so-called quasi-clique . In this work, we demonstrate how two previously existing definitions of quasi-cliques can be unified and how the resulting, more general quasi-clique finding problem can be solved by extending two state-of-the-art stochastic local search algorithms for the classical maximum clique problem. Preliminary results for these algorithms applied to both, artificial and real-world problem instances demonstrate the usefulness of the new quasi-clique definition and the effectiveness of our algorithms. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-92695-5_4 | learning and intelligent optimization |
Keywords | Field | DocType |
general quasi-clique,similarity problem,real-world problem instance,complete subgraph,Effectively Finding Maximal Quasi-cliques,real-world scenario,so-called quasi-clique,new quasi-clique definition,maximum clique,classical problem,classical maximum clique problem | Discrete mathematics,Mathematical optimization,Clique,Maximum common subgraph isomorphism problem,Clique graph,Computer science,Induced subgraph isomorphism problem,Local search (optimization),Clique (graph theory),Clique problem,Subgraph isomorphism problem | Conference |
Volume | ISSN | Citations |
5313 | 0302-9743 | 24 |
PageRank | References | Authors |
1.04 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mauro Brunato | 1 | 405 | 33.73 |
| Holger H. Hoos | 2 | 5327 | 308.70 |
| Roberto Battiti | 3 | 1937 | 262.40 |