Back to Search
Start Over
A branch-and-bound approach for maximum quasi-cliques.
- Source :
-
Annals of Operations Research . May2014, Vol. 216 Issue 1, p145-161. 17p. - Publication Year :
- 2014
-
Abstract
- Detecting quasi-cliques in graphs is a useful tool for detecting dense clusters in graph-based data mining. Particularly in large-scale data sets that are error-prone, cliques are overly restrictive and impractical. Quasi-clique detection has been accomplished using heuristic approaches in various applications of graph-based data mining in protein interaction networks, gene co-expression networks, and telecommunication networks. Quasi-cliques are not hereditary, in the sense that every subset of a quasi-clique need not be a quasi-clique. This lack of heredity introduces interesting challenges in the development of exact algorithms to detect maximum cardinality quasi-cliques. The only exact approaches for this problem are limited to two mixed integer programming formulations that were recently proposed in the literature. The main contribution of this article is a new combinatorial branch-and-bound algorithm for the maximum quasi-clique problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02545330
- Volume :
- 216
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Annals of Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 95093331
- Full Text :
- https://doi.org/10.1007/s10479-012-1242-y