Bibliography

Download the complete bibliography in BibTeX format, or the single BibTeX entries below. A paper can belong to different categories. In each category papers are sorted from the most recent to the oldest. This commented bibliography (252 references for the time being) does not aim at being complete and is currently under construction.
Applications are labeled with the research field name or the research topic.

References to algorithms for the Maximum Independent set (or Maximum Stable Set) are also reported. The Maximum Independent Set is the same problem as the Maximum Clique on the complementary graph, and algorithms can be easily applied to both problems by switching a logical condition in the code. The Maximum Clique literature has been recently richer than the Maximum Independent Set literature and most of the algorithms have been proposed as Maximum Clique solvers.

1 Maximum Clique

1.1 Surveys / Theory

Qinghua Wu and Jin-Kao Hao. A review on algorithms for maximum clique problems. European Journal of Operational Research, 242(3):693—709, 2015.
S. Akbari, M. Aryapoor, and M. Jamaali. Chromatic number and clique number of subgraphs of regular graph of matrix algebras. Linear Algebra and Its Applications, 436(7):2419—2424, 2012. Restriction to graph class having special properties.
Türker Bıyıkoğlu and Josef Leydold. Graphs of given order and size and minimum algebraic connectivity. Linear Algebra and Its Applications, 436(7):2067—2077, 2012. Restriction to graph class having special properties.
Carmen Ortiz and Mónica Villanueva. Maximal independent sets in caterpillar graphs. Discrete Applied Mathematics, 160(3):259—266, 2012. [Maximum Independent Set] Restriction to graph class having special properties.
Sándor Szabó. Parallel algorithms for finding cliques in a graph. Journal of Physics: Conference Series, 268(1):012030, 2011.
Tatsuya Akutsu Etsuji Tomita and Tsutomu Matsunaga. Efficient algorithms for finding maximum and maximal cliques: Effective tools for bioinformatics. ISBN 978-953-307-475-7
David Eppstein, Marteen Löffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, Algorithms and Computation, volume 6506 of Lecture Notes in Computer Science, pages 403—414. Springer Berlin / Heidelberg, 2010.
Note: Variation of BronK:1973 with nodes ordered by degeneracy \(d\), which runs in \(O(dn3^{d/3})\). The algorithm can be applied to large graphs with low degeneracy number (see EppsteinS:2011).
Sergiy Butenko and Wilbert E. Wilhelm. Clique-detection models in computational biochemistry and genomics. European Journal of Operational Research, 173(1):1—17, 2006.
Note: Survey on relevant problems in bioinformatics and biochemistry that can be formalised as graph problems and solved with clique-detection models.
Tobias Storch. How randomized search heuristics find maximum cliques in planar graphs. In GECCO 2006 - Genetic and Evolutionary Computation Conference, volume 1, pages 567—574, New York, NY, USA, 2006. ACM. Restriction to graph class having special properties.
Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1):28—42, 2006.
Note: Theoretical work on worst case complexity of generating all maximal cliques with a depth-first search algorithm. The exact algorithm has a pruning methods that are similar to the Bron-Kerbosh algorithm (BronK:1973), and a different, more compact, representation of the enumerated maximal cliques. The algorithm has \(O(3^{n/3})\) worst-case time complexity for enumerating all maximal cliques (which is optimal).
Immanuel M. Bomze, Marco Budinich, Panos M. Pardalos, and Marcello Pelillo. The maximum clique problem. Handbook of Combinatorial Optimization (Supplement Volume A), 4:1—74, 1999.
Note: Most recent complete survey on the maximum clique formulations, generalisations, algorithms and applications.
Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, pcps, and nonapproximability - towards tight results. SIAM Journal on Computing, 27(3):804—915, 1998.
Johan Håstad. Clique is hard to approximate within \(n^{1-\epsilon}\). In Proceedings of 37th Ann. IEEE Symp. on Foundations of Computer Science, pages 627—636. IEEE Computer Society, 1996.
Panos M. Pardalos and Jue Xue. The maximum clique problem. Journal of Global Optimization, 4(3):301—328, 1994.
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. ISBN 978-0716710455
Note: Classic book on NP-completeness.
David W. Matula. The largest clique size in a random graph. Technical Report CS 7608, Department of Computer Science, Southern Methodist University, 1976
Coen Bron and Joep Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Communications of ACM, 16(9):575—577, sep 1973.
Note: Exact algorithm very popular in computational chemistry and other application domains. Variants with special pivoting rules are among the best performing exact algorithms for the problem. Being complete, it can be applied only to very small instances or to larger instances with small degeneracy number (see EppsteinS:2011).
Richard M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85—103. Plenum Press, 1972.
Note: Historical paper in which Karp presents 21 NP-complete decision problems and reductions among them.

1.1.1 Bounds

Igor Dukanovic and Franz Rendl. Semidefinite programming relaxations for graph coloring and maximal clique problems. Mathematical Programming, 109:345—365, 2007.
Javier Peña, Juan Vera, and Luis F. Zuluaga. Computing the stability number of a graph via linear and semidefinite programming. SIAM Journal on Optimization, 18(1):87—105, 2007.
Nebojša Gvozdenović and Monique Laurent. Semidefinite bounds for the stability number of a graph via sums of squares of polynomials. Integer Programming and Combinatorial Optimization, pages 285—294, 2005.
Etienne de Klerk and Dmitrii V. Pasechnik. Approximation of the stability number of a graph via copositive programming. SIAM Journal on Optimization, 12(4):875—892, 2002.
Subhash Khot. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 600—609. IEEE, 2001.
Alexander Schrijver. A comparison of the delsarte and lovász bounds. Information Theory, IEEE Transactions on, 25(4):425—429, 1979.

1.2 Stochastic Local Search algorithms

Yan Jin and Jin-Kao Hao. General swap-based multiple neighborhood tabu search for the maximum independent set problem. Engineering Applications of Artificial Intelligence, 37:20—33, 2015.
Franco Mascia, Paola Pellegrini, Mauro Birattari, and Thomas Stützle. An analysis of parameter adaptation in reactive tabu search. International Transactions in Operational Research, 21(1):127—152, jan 2014.
Note: In depth analysis of the dynamics of reactive tabu search focussing on the maximum clique problem (BattitiM:2010), and quadratic assignment problem. It also presents an analysis of the DIMACS instances and the first optimal solution with 1100 nodes for MANN_a81.
Una Benlic and Jin-Kao Hao. Breakout local search for maximum clique problems. Computers and Operations Research, 40(1):192—206, 2013.
Qinghua Wu and Jin-Kao Hao. An adaptive multistart tabu search approach to solve the maximum clique problem. Journal of Combinatorial Optimization, 26(1):86—108, 2013.
Ben-Da Zhou, Hong-Liang Yao, Ming-Hua Shi, Qin Yue, and Hao Wang. An new immune genetic algorithm based on uniform design sampling. Knowledge and Information Systems, pages 1—15, 2012.
Mohammad M. Javidi and Saeed Mehrabi. On evolutionary algorithms for large cliques in random graphs. International Journal of Applied Mathematics and Statistics, 22(SUPPL. 11):53—60, 2011.
Wayne Pullan, Franco Mascia, and Mauro Brunato. Cooperating local search for the maximum clique problem. Journal of Heuristics, 17(2):181—199, apr 2011.
Note: Parallel meta-heuristic with state-of-the-art results on DIMACS and BHOSLIB instances. Components are a greedy reactive tabu search component (BattitiM:2010), a penalty-based dynamic local search (PullanH:2006), and a focussed meta-heuristic that focusses on cliques having nodes with a specific degree.
Roberto Battiti and Franco Mascia. Reactive and dynamic local search for max-clique: Engineering effective building blocks. Computers and Operations Research, 37(3):534—542, mar 2010.
Note: Latest implementation of the original reactive tabu search for the maximum clique problem (BattitiP:2001). It is a parameter free algorithm which is state-of-the-art results on DIMACS instances.
Duc-Cuong Dang and Aziz Moukrim. Subgraph extraction and memetic algorithm for the maximum clique problem. In ICEC 2010 - Proceedings of the International Conference on Evolutionary Computation, pages 77—84. INSTICC, 2010.
Shalini Rajawat, Naveen Hemrajani, and Ekta Menghani. Solving maximal clique problem through genetic algorithm. In R. B. Patel and B. P. Singh, editors, AIP Conference Proceedings, volume 1324, pages 235—238. American Institute of Physics, 2010.
Shijun Ren and Yadong Wang. An improved aco metaheuristic for solving the mcp. In Proceedings - 2010 6th International Conference on Natural Computation, ICNC 2010, volume 1, pages 106—111, 2010.
Thang N. Bui, ThanhVu Nguyen, and Joseph R. Rizzo Jr. Parallel shared memory strategies for ant-based optimization algorithms. In Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009, pages 1—8, New York, NY, USA, 2009. ACM.
Andrea Grosso, Marco Locatelli, and Wayne Pullan. Simple ingredients leading to very efficient heuristics for the maximum clique problem. Journal of Heuristics, 14(6):587—612, oct 2007.
Note: Parameter free meta-heuristic. First optimal solution of size 80 for the DIMACS instance C2000.9.
Hassan Younies and George O. Wesolowsky. Planar maximal covering location problem under block norm distance measure. Journal of the Operational Research Society, 58(6):740—750, 2007. Clique Partitioning Problem
Qingfu Zhang, Jianyong Sun, and Edward Tsang. Combinations of estimation of distribution algorithms and other techniques. ISSN 1476-8186
Wayne Pullan. Phased local search for the maximum clique problem. Journal of Combinatorial Optimization, 12(3):303—323, 2006.
Note: Portfolio of meta-heuristics applied sequentially, with adaptive setting of the penalty delay parameter of (PullanH:2006).
Wayne Pullan and Holger H. Hoos. Dynamic local search for the maximum clique problem. Journal of Artificial Intelligence Research, 25(1):159—185, 2006.
Note: Penalty based non-greedy meta-heuristic with state-of-the-art performance on the DIMACS benchmark set.
Alok Singh and Ashok Kumar Gupta. A hybrid heuristic for the maximum clique problem. Journal of Heuristics, 12(1-2):5—22, 2006.
Christine Solnon and Serge Fenet. A study of aco capabilities for solving the maximum clique problem. Journal of Heuristics, 12(3):155—180, 2006.
Note: Study on the impact of pheromone trails on the solution process of a memetic algorithm for the maximum clique problem.
Tobias Storch. How randomized search heuristics find maximum cliques in planar graphs. In GECCO 2006 - Genetic and Evolutionary Computation Conference, volume 1, pages 567—574, New York, NY, USA, 2006. ACM. Restriction to graph class having special properties.
Kengo Katayama, Akihiro Hamamoto, and Hiroyuki Narihisa. An effective local search for the maximum clique problem. Information Processing Letters, 95(5):503—511, 2005.
Xiaoming Liu, Jianwei Yin, Jung-Sing Jwo, Zhilin Feng, and Jinxiang Dong. A dna-based genetic algorithm implementation for graph coloring problem. In De-Shuang Huang, Xiao-Ping Zhang, and Guang-Bin Huang, editors, Advances in Intelligent Computing, volume 3645 of Lecture Notes in Computer Science, pages 99—108. Springer Berlin / Heidelberg, 2005.
C. Y. Sun, W. J. Li, and X. Z. Gao. A novel evolutionary algorithm for mcp using mec. In SMCia/05 - Proceedings of the 2005 IEEE Mid-Summer Workshop on Soft Computing in Industrial Applications, volume 2005, pages 99—104, 2005.
Qingfu Zhang, Jianyong Sun, and Edward Tsang. An evolutionary algorithm with guided mutation for the maximum clique problem. Evolutionary Computation, IEEE Transactions on, 9(2):192—200, 2005.
Andrea Grosso, Marco Locatelli, and Federico Della Croce. Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem. Journal of Heuristics, 10(2):135—152, 2004.
Pierre Hansen, Nenad Mladenović, and Dragan Urošević. Variable neighborhood search for the maximum clique. Discrete Applied Mathematics, 145(1):117—125, 2004.
Kengo Katayama, Akihiro Hamamoto, and Hiroyuki Narihisa. Solving the maximum clique problem by k-opt local search. In Proceedings of the ACM Symposium on Applied Computing, volume 2, pages 1021—1025, New York, NY, USA, 2004. ACM.
Sherin M. Youssef and Dave G. Elliman. Reactive prohibition-based ant colony optimization (rpaco): A new parallel architecture for constrained clique sub-graphs. In Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI, pages 63—70. IEEE, 2004.
Jean-Charles Regin. Solving the maximum clique problem with constraint programming. In Fifth International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR’03), May 8-10, 2003, Montreal, Canada., pages 166—179, 2003.
Elena Marchiori. Genetic, iterated and multistart local search for the maximum clique problem. In Stefano Cagnoni, Jens Gottlieb, Emma Hart, Martin Middendorf, and Günther Raidl, editors, Applications of Evolutionary Computing, volume 2279 of Lecture Notes in Computer Science, pages 112—121. Springer Berlin / Heidelberg, 2002.
Roberto Battiti and Marco Protasi. Reactive local search for the maximum clique problem. Algorithmica, 29(4):610—637, apr 2001.
Note: Original reactive tabu search for the maximum clique problem. BattitiM:2010, is the updated version with small implementation and algorithmic improvements, which is, on large instances, one order of magnitude faster.
Immanuel M. Bomze and Volker Stix. Genetic engineering via negative fitness:evolutionary dynamics for global optimization. ISSN 0254-5330
Patrick Soriano and Michel Gendreau. Diversification strategies in tabu search algorithms for the maximum clique problem. ISSN 0254-5330
Thang Nguyen Bui and Paul H. Eppley. A hybrid genetic algorithm for the maximum clique problem. In Proceedings of the 6th international conference on genetic algorithms, pages 478—484, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.
Thomas Bäck and Sami Khuri. An evolutionary heuristic for the maximum independent set problem. In Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on, pages 531—535. IEEE, 1994. [Maximum Independent Set]
Robert Carter and Kihong Park. How good are genetic algorithms at finding large cliques: an experimental study. Technical report, Boston University Computer Science Department, 1993
Michel Gendreau, Patrick Soriano, and Louis Salvail. Solving the maximum clique problem using a tabu search approach. Annals of Operations Research, 41(4):385—403, 1993.
C. Friden, A. Hertz, and D. Werra. Stabulus: a technique for finding stable sets in large graphs with tabu search. Computing, 42(1):35—44, 1989. [Maximum Independent Set]

1.3 Applications

Carina Curto, Anda Degeratu, and Vladimir Itskov. Flexible memory networks. Bulletin of Mathematical Biology, 74(3):590—614, mar 2012. [neuroscience]
Seung Kwan Kim, Jee Hyung Lee, Keun Ho Ryu, and Ungmo Kim. A framework of spatial co-location pattern mining for ubiquitous gis. Multimedia Tools and Applications, pages 1—20, 2012. [spatial data mining]
Xiaoke Ma and Lin Gao. Predicting protein complexes in protein interaction networks using a core-attachment algorithm based on graph communicability. Information Sciences, 189:233—254, 2012. [bioinformatics - proteomics - protein complexes]
Dana M. Sepe, Thomas McWilliams, Jinbo Chen, Aaron Kershenbaum, Huaqing Zhao, Mei La, Meenakshi Devidas, Beverly Lange, Timothy R. Rebbeck, and Richard Aplenc. Germline genetic variation and treatment response on ccg-1891. Pediatric Blood & Cancer, 58(5):695—700, may 2012. [medicine - gene-gene interaction networks]
S. Joshua Swamidass, Bradley T. Calhoun, Joshua A. Bittker, Nicole E. Bodycombe, and Paul A. Clemons. Utility-aware screening with clique-oriented prioritization. Journal of Chemical Information and Modeling, 52(1):29—37, jan 2012. [chemistry / molecular biology - high-throughput-screening]
Sanjeev Arora, Rong Ge, Sushant Sachdeva, and Grant Schoenebeck. Finding overlapping communities in social networks: Toward a rigorous approach. CoRR, abs/1112.1831, 2011.
Sankar Basu, Dhananjay Bhattacharyya, and Rahul Banerjee. Mapping the distribution of packing topologies within protein interiors shows predominant preference for specific packing motifs. BMC Bioinformatics, 12:195, 2011.
Ming-Huang Chen, Wu-Lung R. Yang, Kuan-Ting Lin, Chia-Hung Liu, Yu-Wen Liu, Kai-Wen Huang, Peter Mu-Hsin Chang, Jin-Mei Lai, Chun-Nan Hsu, Kun-Mao Chao, Cheng-Yan Kao, and Chi-Ying F. Huang. Gene expression-based chemical genomics identifies potential therapeutic drugs in hepatocellular carcinoma. Plos One, 6(11):e27186, 2011.
Daiji Fukagawa, Takeyuki Tamura, Atsuhiro Takasu, Etsuji Tomita, and Tatsuya Akutsu. A clique-based method for the edit distance between unordered trees and its application to analysis of glycan structures. BMC Bioinformatics, 12 Suppl 1:S13, 2011.
Hiroshi Ishikawa. Transformation of general binary mrf minimization to the first-order case. IEEE Transactions On Pattern Analysis and Machine Intelligence, 33(6):1234—49, jun 2011.
Qing-Ju Jiao, Yan Huang, and Hong-Bin Shen. Large-scale mining co-expressed genes in arabidopsis anther: from pair to group. Computational Biology and Chemistry, 35(2):62—8, apr 2011.
Takeshi Kawabata. Build-up algorithm for atomic correspondence between chemical structures. Journal of Chemical Information and Modeling, 51(8):1775—87, aug 2011.
Conrad Lee, Fergal Reid, Aaron McDaid, and Neil Hurley. Seeding for pervasively overlapping communities. Phys. Rev. E, 83(6):066107, 2011.
Sheng-An Lee, Theresa Tsun-Hui Tsao, Ko-Chun Yang, Han Lin, Yu-Lun Kuo, Chien-Hsiang Hsu, Wen-Kuei Lee, Kuo-Chuan Huang, and Cheng-Yan Kao. Construction and analysis of the protein-protein interaction networks for schizophrenia, bipolar disorder, and major depression. BMC Bioinformatics, 12 Suppl 13:S20, nov 2011.
Xia Li, Chunquan Li, Desi Shang, Jing Li, Junwei Han, Yingbo Miao, Yan Wang, Qianghu Wang, Wei Li, Chao Wu, Yunpeng Zhang, Xiang Li, and Qianlan Yao. The implications of relationships between human diseases and metabolic subpathways. Plos One, 6(6):e21131, 2011.
Pedro Nunez, Ricardo Vazquez-Martin, and Antonio Bandera. Visual odometry based on structural matching of local invariant features using stereo camera sensor. Sensors, 11(7):7262—84, 2011.
Alex Rodionov, Alexandr Bezginov, Jonathan Rose, and Elisabeth Rm Tillier. A new, fast algorithm for detecting protein coevolution using maximum compatible cliques. Algorithms for Molecular Biology, 6:17, 2011.
Matthew C. Schmidt, Andrea M. Rocha, Kanchana Padmanabhan, Zhengzhang Chen, Kathleen Scott, James R. Mihelcic, and Nagiza F. Samatova. Efficient alpha, beta-motif finder for identification of phenotype-related functional modules. BMC Bioinformatics, 12:440, 2011.
Elizabeth Skippington and Mark A. Ragan. Lateral genetic transfer and the construction of genetic exchange communities. Fems Microbiology Reviews, 35(5):707—35, sep 2011.
I-Lin Wang and Chia-Yuan Chang. Mathematical properties and bounds on haplotyping populations by pure parsimony. Mathematical Biosciences, 231(2):120—5, jun 2011.
Michael Wels, Yefeng Zheng, Martin Huber, Joachim Hornegger, and Dorin Comaniciu. A discriminative model-constrained em approach to 3d mri brain tissue classification and intensity non-uniformity correction. Physics in Medicine and Biology, 56(11):3269—300, jun 2011.
Yan Yan, Shenggui Zhang, and Fang-Xiang Wu. Applications of graph theory in protein structure identification. Proteome Science, 9 Suppl 1:S17, 2011.
Zhanli Zhang, Xin Jiang, Lili Ma, Shaoting Tang, and Zhiming Zheng. Detecting communities in clustered networks based on group action on set. Physica A: Statistical Mechanics and its Applications, 390(6):1171—1181, 2011.
Hongyan Zhang and Xiyu Liu. A clique algorithm using dna computing techniques based on closed-circle dna sequences. Bio Systems, 105(1):73—82, jul 2011.
Xiaoqi Zheng, Taigang Liu, Zhongnan Yang, and Jun Wang. Large cliques in arabidopsis gene coexpression network and motif discovery. Journal of Plant Physiology, 168(6):611—8, apr 2011.
Ashis Kumer Biswas, Nasimul Noman, and Abdur Rahman Sikder. Machine learning approach to predict protein phosphorylation sites by incorporating evolutionary information. BMC Bioinformatics, 11:273, 2010.
Rick C. S Chen and Stephen J. H. Yang. Applying dna computation to intractable problems in social network analysis. Bio Systems, 101(3):222—32, sep 2010.
David L. Cooper, James E. Gentle, Ernest Barreto, and James L. Olds. Synchronized changes to relative neuron populations in postnatal human neocortical development. Cognitive Neurodynamics, 4(2):151—63, jun 2010.
Ryan Day, Kristin P. Lennox, David B. Dahl, Marina Vannucci, and Jerry W. Tsai. Characterizing the regularity of tetrahedral packing motifs in protein tertiary structure. Bioinformatics, 26(24):3059—66, dec 2010.
Janez Konc and Dusanka Janezic. Probis algorithm for detection of structurally similar protein binding sites by local structural alignment. Bioinformatics, 26(9):1160—8, may 2010.
M. Pawan Kumar, P. H S. Torr, and A. Zisserman. Objcut: efficient segmentation using top-down and bottom-up cues. IEEE Transactions On Pattern Analysis and Machine Intelligence, 32(3):530—45, mar 2010.
Ming-Ying Lan, Chi-Long Chen, Kuan-Ting Lin, Sheng-An Lee, Wu-Lung R. Yang, Chun-Nan Hsu, Jaw-Ching Wu, Ching-Yin Ho, Jin-Ching Lin, and Chi-Ying F. Huang. From npc therapeutic target identification to potential treatment strategy. Molecular Cancer Therapeutics, 9(9):2511—23, sep 2010.
Min Li, Jianxin Wang, Jianer Chen, Zhao Cai, and Gang Chen. Identifying the overlapping complexes in protein interaction networks. International Journal of Data Mining and Bioinformatics (IJDMB), 4(1):91—108, 2010.
Ryan R. Rahrig, Neocles B. Leontis, and Craig L. Zirbel. R3d align: global pairwise alignment of rna 3d structures using local superpositions. Bioinformatics, 26(21):2689—97, nov 2010.
Felix Reisen, Martin Weisel, Jan M. Kriegl, and Gisbert Schneider. Self-organizing fuzzy graphs for structure-based comparison of protein pockets. Journal of Proteome Research, 9(12):6498—510, dec 2010.
Zhiao Shi, Catherine K. Derow, and Bing Zhang. Co-expression module analysis reveals biological processes, genomic gain, and regulatory mechanisms associated with breast cancer progression. BMC Systems Biology, 4:74, 2010.
Shellie R. Simons and Barbara Mawn. Bullying in the workplace—a qualitative study of newly licensed registered nurses. Aaohn Journal, 58(7):305—11, jul 2010.
Jianxin Wang, Binbin Liu, Min Li, and Yi Pan. Identifying protein complexes from interaction networks based on clique percolation and distance restriction. BMC Genomics, 11(Suppl 2):S10, 2010.
Miranda Witvliet, Mara Brendgen, Pol A. C van Lier, Hans M. Koot, and Frank Vitaro. Early adolescent depressive symptoms: prediction from clique isolation, loneliness, and perceived social acceptance. Journal of Abnormal Child Psychology, 38(8):1045—56, nov 2010.
Miranda Witvliet, Pol A. C van Lier, Mara Brendgen, Hans M. Koot, and Frank Vitaro. Longitudinal associations between clique membership status and internalizing and externalizing problems during late childhood. Journal of Clinical Child and Adolescent Psychology, 39(5):693—704, 2010.
Miranda Witvliet, Pol A. C van Lier, Pim Cuijpers, and Hans M. Koot. Change and stability in childhood clique membership, isolation from cliques, and associated child characteristics. Journal of Clinical Child and Adolescent Psychology, 39(1):12—24, 2010.
Yi Yang, Dong Xu, Feiping Nie, Shuicheng Yan, and Yueting Zhuang. Image clustering using local discriminant models and global integration. IEEE Transactions On Image Processing, 19(10):2761—73, oct 2010.
Corin Yeats, Oliver C. Redfern, and Christine Orengo. A fast and automated solution for accurately resolving protein domain architectures. Bioinformatics, 26(6):745—51, mar 2010.
Kun Zhao, Shao-Wu Zhang, and Quan Pan. Fuzzy analysis for overlapping community structure of complex network. In Control and Decision Conference (CCDC), 2010 Chinese, pages 3976—3981. IEEE Computer Society, 2010.
David Barber. Identifying graph clusters using variational inference and links to covariance parametrization. Philosophical Transactions. Series A, Mathematical, Physical, and Engineering Sciences, 367(1906):4407—26, nov 2009.
Tiberio S. Caetano and Julian J. McAuley. Faster graphical models for point-pattern matching. Spatial Vision, 22(5):443—53, 2009.
Jiun-Rung Chen and Ye-In Chang. A condition-enumeration tree method for mining biclusters from dna microarray data sets. Bio Systems, 97(1):44—59, jul 2009.
Majid Darehmiraki. A new solution for maximal clique problem based sticker model. Bio Systems, 95(2):145—9, feb 2009.
Dhruba Deb, Saraswathi Vishveshwara, and Smitha Vishveshwara. Understanding protein structure from a percolation perspective. Biophysical Journal, 97(6):1787—94, sep 2009.
Sarosh N. Fatakia, Stefano Costanzi, and Carson C. Chow. Computing highly correlated positions using mutual information and graph theory for g protein-coupled receptors. Plos One, 4(3):e4681, 2009.
Eleanor J. Gardiner, David A. Cosgrove, Robin Taylor, and Valerie J. Gillet. Multiobjective optimization of pharmacophore hypotheses: bias toward low-energy conformations. Journal of Chemical Information and Modeling, 49(12):2761—73, dec 2009.
Thomas T. Hills, Mounir Maouene, Josita Maouene, Adam Sheya, and Linda Smith. Categorical structure among shared features in networks of early-learned nouns. Cognition, 112(3):381—96, sep 2009.
Pushmeet Kohli, M. Pawan Kumar, and Philip H. S. Torr. P3 & beyond: move making algorithms for solving higher order functions. IEEE Transactions On Pattern Analysis and Machine Intelligence, 31(9):1645—56, sep 2009.
Jing Li, Lisa J. Zimmerman, Byung-Hoon Park, David L. Tabb, Daniel C. Liebler, and Bing Zhang. Network-assisted protein identification and data interpretation in shotgun proteomics. Molecular Systems Biology, 5:303, 2009.
Chen-Ching Lin, Hsueh-Fen Juan, Jen-Tsung Hsiang, Yih-Chii Hwang, Hirotada Mori, and Hsuan-Cheng Huang. Essential core of protein-protein interaction network in escherichia coli. Journal of Proteome Research, 8(4):1925—31, apr 2009.
Ville-Petteri Makinen, Carol Forsblom, Lena M. Thorn, Johan Waden, Kimmo Kaski, Mika Ala-Korpela, and Per-Henrik Groop. Network of vascular diseases, death and biochemical characteristics in a set of 4,197 patients with type 1 diabetes (the finndiane study). Cardiovascular Diabetology, 8:54, 2009.
Linyong Mao, John L. Van Hemert, Sudhansu Dash, and Julie A. Dickerson. Arabidopsis gene co-expression network and its functional modules. BMC Bioinformatics, 10:346, 2009.
Tsutomu Matsunaga, Chikara Yonemori, Etsuji Tomita, and Masaaki Muramatsu. Clique-based data mining for related genes in a biomedical database. BMC Bioinformatics, 10:205, 2009.
Richard A. Mushlin, Stephen Gallagher, Aaron Kershenbaum, and Timothy R. Rebbeck. Clique-finding for heterogeneity and multidimensionality in biomarker epidemiology research: the chamber algorithm. Plos One, 4(3):e4862, 2009.
Georgios A. Pavlopoulos, Charalampos N. Moschopoulos, Sean D. Hooper, Reinhard Schneider, and Sophia Kossida. jclust: a clustering and visualization toolbox. Bioinformatics, 25(15):1994—6, aug 2009.
Yevgeniy Podolyan and George Karypis. Common pharmacophore identification using frequent clique detection algorithm. Journal of Chemical Information and Modeling, 49(1):13—21, jan 2009.
John Thomas, Naren Ramakrishnan, and Chris Bailey-Kellogg. Protein design by sampling an undirected graphical model of residue constraints. IEEE/Acm Transactions On Computational Biology and Bioinformatics / IEEE, Acm, 6(3):506—16, jul 2009.
Thiago M. Venancio, S. Balaji, Lakshminarayan M. Iyer, and L. Aravind. Reconstructing the ubiquitin network: cross-talk with other systems and identification of novel functions. Genome Biology, 10(3):R33, 2009.
Stefan Wuchty, John H. Adams, and Michael T. Ferdig. A comprehensive plasmodium falciparum protein interaction map reveals a distinct architecture of a core interactome. Proteomics, 9(7):1841—9, apr 2009.
Yuanyuan Xiao and Mark R. Segal. Identification of yeast transcriptional regulation networks using multivariate random forests. Plos Computational Biology, 5(6):e1000414, jun 2009.
Huanping Zhang, Xiaofeng Song, Huinan Wang, and Xiaobai Zhang. Miclique: An algorithm to identify differentially coexpressed disease gene subset from microarray data. Journal of Biomedicine & Biotechnology, 2009:642524, 2009.
Michelle Bezanson, Paul A. Garber, John T. Murphy, and L. S. Premo. Patterns of subgrouping and spatial affiliation in a community of mantled howling monkeys (alouatta palliata). American Journal of Primatology, 70(3):282—93, mar 2008.
George Jr Chin, Daniel G. Chavarria, Grant C. Nakamura, and Heidi J. Sofia. Biographe: high-performance bionetwork analysis using the biological graph environment. BMC Bioinformatics, 9 Suppl 6:S6, 2008.
Guangyu Cui, Yu Chen, De-Shuang Huang, and Kyungsook Han. An algorithm for finding functional modules and protein complexes in protein-protein interaction networks. Journal of Biomedicine & Biotechnology, 2008:860270, 2008.
John C. Cushman, Richard L. Tillett, Joshua A. Wood, Joshua M. Branco, and Karen A. Schlauch. Large-scale mrna expression profiling in the common ice plant, mesembryanthemum crystallinum, performing c3 photosynthesis and crassulacean acid metabolism (cam). Journal of Experimental Botany, 59(7):1875—94, 2008.
Amit Ghosh and Saraswathi Vishveshwara. Variations in clique and community patterns in protein structures during allosteric communication: investigation of dynamically equilibrated structures of methionyl trna synthetase complexes. Biochemistry, 47(44):11398—407, nov 2008.
Parthasarathy Guturu and Ram Dantu. An impatient evolutionary algorithm with probabilistic tabu search for unified solution of some np-hard problems in graph and set theory via clique finding. IEEE Transactions On Systems, Man, and Cybernetics. Part B, Cybernetics, 38(3):645—66, jun 2008.
Seong-Eui Hong, Inju Park, Hyeseon Cha, Seong-Hwan Rho, Woo Jin Park, Chunghee Cho, and Do Han Kim. Identification of mouse heart transcriptomic network sensitive to various heart diseases. Biotechnology Journal, 3(5):648—58, may 2008.
Tianyun Liu, Michal Guerquin, and Ram Samudrala. Improving the accuracy of template-based predictions by mixing and matching between initial models. BMC Structural Biology, 8:24, 2008.
Fan Liu, Anatoliy Kirichenko, Tatiana I. Axenovich, Cornelia M. van Duijn, and Yurii S. Aulchenko. An approach for cutting large and complex pedigrees for linkage analysis. European Journal of Human Genetics, 16(7):854—60, jul 2008.
Julian J. McAuley, Tiberio S. Caetano, and Marconi S. Barbosa. Graph rigidity, cyclic belief propagation, and point pattern matching. IEEE Transactions On Pattern Analysis and Machine Intelligence, 30(11):2047—54, nov 2008.
Yanjun Qi, Fernanda Balem, Christos Faloutsos, Judith Klein-Seetharaman, and Ziv Bar-Joseph. Protein complex identification by supervised graph local clustering. Bioinformatics, 24(13):i250—8, jul 2008.
Mehmet E. Turanalp and Tolga Can. Discovering functional interaction patterns in protein-protein interaction networks. BMC Bioinformatics, 9:276, 2008.
Jia Zeng and Zhi-Qiang Liu. Markov random field-based statistical character structure modeling for handwritten chinese character recognition. IEEE Transactions On Pattern Analysis and Machine Intelligence, 30(5):767—80, may 2008.
Michael ten Caat, Natasha M. Maurits, and Jos B. T M. Roerdink. Data-driven visualization and group analysis of multichannel eeg coherence with functional units. IEEE Transactions On Visualization and Computer Graphics, 14(4):756—71, jul 2008.
Carlos M. Carvalho, Hélène Massam, and Mike West. Simulation of hyper-inverse {W}ishart distributions in graphical models. Biometrika, 94(3):647—659, 2007. [graphical models]
Antoine Danchin, Gang Fang, and Stanislas Noria. The extant core bacterial proteome is an archive of the origin of life. Proteomics, 7(6):875—89, mar 2007.
Nan Du, Bin Wu, Xin Pei, Bai Wang, and Liutong Xu. Community detection in large-scale social networks. ISBN 978-1-59593-848-0
Giacomo Finocchiaro, Francesco Mattia Mancuso, Davide Cittaro, and Heiko Muller. Graph-based identification of cancer signaling pathways from published gene expression signatures using publime. Nucleic Acids Research, 35(7):2343—55, 2007.
Marc Garcia-Arnau, Daniel Manrique, Alfonso Rodriguez-Paton, and Petr Sosik. A p system and a constructive membrane-inspired dna algorithm for solving the maximum clique problem. Bio Systems, 90(3):687—97, nov 2007.
Andrew C. Good. Novel dock clique driven 3d similarity database search tools for molecule shape matching and beyond: adding flexibility to the search for ligand kin. Journal of Molecular Graphics & Modelling, 26(3):656—66, oct 2007.
Radhey S. Gupta and Emily Lorenzini. Phylogeny and molecular signatures (conserved proteins and indels) that are specific for the bacteroidetes and chlorobi species. BMC Evolutionary Biology, 7:71, 2007.
Radhey S. Gupta and Peter H. A. Sneath. Application of the character compatibility approach to generalized molecular sequence data: branching order of the proteobacterial subdivisions. Journal of Molecular Evolution, 64(1):90—100, jan 2007.
Delyse M. Hutchinson and Ronald M. Rapee. Do friends share similar body image and eating problems? the role of social networks and peer influences in early adolescence. Behaviour Research and Therapy, 45(7):1557—77, jul 2007.
Alan Ironmonger, Benjamin Whittaker, Andrew J. Baron, Blandine Clique, Chris J. Adams, Alison E. Ashcroft, Peter G. Stockley, and Adam Nelson. Scanning conformational space with a library of stereo- and regiochemically diverse aminoglycoside derivatives: the discovery of new ligands for rna hairpin sequences. Organic & Biomolecular Chemistry, 5(7):1081—6, apr 2007.
Gergely Palla, Albert-Laszlo Barabasi, and Tamas Vicsek. Quantifying social group evolution. Nature, 446(7136):664—7, apr 2007.
Oleg Rokhlenko, Ydo Wexler, and Zohar Yakhini. Similarities and differences of gene expression in yeast stress conditions. Bioinformatics, 23(2):e184—90, jan 2007.
Joe Z. Tsien. Real-time neural coding of memory. Progress in Brain Research, 165:105—22, 2007.
Hassan Younies and George O. Wesolowsky. Planar maximal covering location problem under block norm distance measure. Journal of the Operational Research Society, 58(6):740—750, 2007. [planar maximal covering location problem] Clique Partitioning Problem
Chunfang Zheng, Qian Zhu, and David Sankoff. Removing noise and ambiguities from comparative maps in rearrangement analysis. IEEE/Acm Transactions On Computational Biology and Bioinformatics / IEEE, Acm, 4(4):515—22, oct 2007.
Balázs Adamcsek, Gergely Palla, Illés J. Farkas, Imre Derényi, and Tamás Vicsek. Cfinder: locating cliques and overlapping modules in biological networks. Bioinformatics, 22(8):1021—1023, 2006.
Edward J. Barker, David Buttar, David A. Cosgrove, Eleanor J. Gardiner, Paula Kitts, Peter Willett, and Valerie J. Gillet. Scaffold hopping using clique detection applied to reduced graphs. Journal of Chemical Information and Modeling, 46(2):503—11, mar 2006.
Vladimir Boginski, Sergiy Butenko, and Panos M. Pardalos. Mining market data: A network approach. Computers & Operations Research, 33(11):3171—3184, 2006.
Jun Feng, Ashish Sanil, and S. Stanley Young. Pharmid: pharmacophore identification using gibbs sampling. Journal of Chemical Information and Modeling, 46(3):1352—9, may 2006.
Kevin Hambly, Joseph Danzer, Steven Muskal, and Derek A. Debe. Interrogating the druggable genome with structural informatics. Molecular Diversity, 10(3):273—81, aug 2006.
Xiuzhen Huang, Jing Lai, and Steven F. Jennings. Maximum common subgraph: some upper bound and lower bound results. BMC Bioinformatics, 7 Suppl 4:S6, 2006.
Woochang Hwang, Young-Rae Cho, Aidong Zhang, and Murali Ramanathan. A novel functional module detection algorithm for protein-protein interaction networks. Algorithms for Molecular Biology, 1:24, 2006.
Chih-Hung Jen, Iain W. Manfield, Ioannis Michalopoulos, John W. Pinney, William G. T Willats, Philip M. Gilmartin, and David R. Westhead. The arabidopsis co-expression tool (act): a www-based tool and database for microarray-based gene expression analysis. The Plant Journal, 46(2):336—48, apr 2006.
Katharina A. Lehmann, Michael Kaufmann, Stephan Steigele, and Kay Nieselt. On the maximal cliques in c-max-tolerance graphs and their application in clustering molecular sequences. Algorithms for Molecular Biology, 1(1), 2006. [clustering, generation of phylogenetic trees]
Longnian Lin, Remus Osan, and Joe Z. Tsien. Organizing principles of real-time memory encoding: neural clique assemblies and universal neural codes. Trends in Neurosciences, 29(1):48—57, jan 2006.
Iain W. Manfield, Chih-Hung Jen, John W. Pinney, Ioannis Michalopoulos, James R. Bradford, Philip M. Gilmartin, and David R. Westhead. Arabidopsis co-expression tool (act): web server tools for microarray-based gene expression analysis. Nucleic Acids Research, 34(Web Server issue):W504—9, jul 2006. [molecular biology - gene expression networks]
Amrita Pati, Cecilia Vasquez-Robinet, Lenwood S. Heath, Ruth Grene, and T. M. Murali. Xcisclique: analysis of regulatory bicliques. BMC Bioinformatics, 7:218, 2006. [molecular biology - gene regulatory networks]
Brynn H. Voy, Jon A. Scharff, Andy D. Perkins, Arnold M. Saxton, Bhavesh Borate, Elissa J. Chesler, Lisa K. Branstetter, and Michael A. Langston. Extracting gene networks for low-dose radiation using graph theoretical algorithms. Plos Computational Biology, 2(7):e89, jul 2006. [molecular biology - gene expression networks]
Haiyuan Yu, Alberto Paccanaro, Valery Trifonov, and Mark Gerstein. Predicting interactions in protein networks by completing defective cliques. Bioinformatics, 22(7):823—9, apr 2006.
Ziding Zhang and Martin G. Grigorov. Similarity networks of protein binding sites. Proteins, 62(2):470—8, feb 2006.
Chi Zhang, Song Liu, and Yaoqi Zhou. Fast and accurate method for identifying high-quality protein-interaction modules by clique merging and its application to yeast. Journal of Proteome Research, 5(4):801—7, apr 2006.
Shihua Zhang, Xuemei Ning, and Xiang-Sun Zhang. Identification of functional modules in a ppi network by clique percolation clustering. Computational Biology and Chemistry, 30(6):445—51, dec 2006.
Normand Carpentier and Francine Ducharme. Support network transformations in the first stages of the caregiver’s career. Qualitative Health Research, 15(3):289—311, mar 2005.
Yu Chen and Gordon M. Crippen. A novel approach to structural alignment using realistic structural and environmental information. Protein Science, 14(12):2935—46, dec 2005.
Ting Chen and Dimitris Metaxas. A hybrid framework for 3d medical image segmentation. Medical Image Analysis, 9(6):547—65, dec 2005.
Blandine Clique, Alan Ironmonger, Benjamin Whittaker, Jacqueline Colley, James Titchmarsh, Peter Stockley, and Adam Nelson. Synthesis of a library of stereo- and regiochemically diverse aminoglycoside derivatives. Organic & Biomolecular Chemistry, 3(15):2776—85, aug 2005.
Imre Derényi, Gergely Palla, and Tamás Vicsek. Clique percolation in random networks. Physical review letters, 94(16):160202, 2005.
Longnian Lin, Remus Osan, Shy Shoham, Wenjun Jin, Wenqi Zuo, and Joe Z. Tsien. Identification of network-level coding units for real-time representation of episodic experiences in the hippocampus. Proceedings of the National Academy of Sciences of the United States of America, 102(17):6125—30, apr 2005.
Heinz Muhlenbein and Robin Hons. The estimation of distributions and the minimum relative entropy principle. Evolutionary Computation, 13(1):1—27, 2005.
David L. Tabb, Melissa R. Thompson, Gurusahai Khalsa-Moyers, Nathan C. VerBerkmoes, and W. Hayes McDonald. Ms2grouper: group assessment and synthetic replacement of duplicate proteomic tandem mass spectra. Journal of the American Society for Mass Spectrometry, 16(8):1250—61, aug 2005.
James R. Arnold, Keith W. Burdick, Scott C-H Pegg, Samuel Toba, Michelle L. Lamb, and Irwin D. Kuntz. Siteprint: three-dimensional pharmacophore descriptors derived from protein binding sites for family based active site analysis, classification, and drug design. Journal of Chemical Information and Computer Sciences, 44(6):2190—8, nov 2004.
Andreas Brakoulias and Richard M. Jackson. Towards a structural classification of phosphate binding sites in protein-nucleotide complexes: an automated all-against-all structural comparison using geometric matching. Proteins, 56(2):250—60, aug 2004.
Mathaus Dejori, Anton Schwaighofer, Volker Tresp, and Martin Stetter. Mining functional modules in genetic networks with decomposable graphical models. Omics, 8(2):176—88, 2004.
Yongmei Ji, Xing Xu, and Gary D. Stormo. A graph theoretical approach for predicting common rna secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics, 20(10):1591—602, jul 2004.
Nils Weskamp, Daniel Kuhn, Eyke Hullermeier, and Gerhard Klebe. Efficient similarity search in protein structure databases by k-clique hashing. Bioinformatics, 20(10):1522—6, jul 2004.
Masahiro Hattori, Yasushi Okuno, Susumu Goto, and Minoru Kanehisa. Development of a chemical structure comparison method for integrated analysis of chemical and genomic information in the metabolic pathways. Journal of the American Chemical Society, 125(39):11853—65, oct 2003.
Kengo Kinoshita and Haruki Nakamura. Identification of protein biochemical functions by similarity search using the molecular surface database ef-site. Protein Science, 12(8):1589—95, aug 2003.
Nicholas Rhodes, Peter Willett, Alain Calvet, James B. Dunbar, and Christine Humblet. Clip: similarity searching of 3d databases using clique detection. Journal of Chemical Information and Computer Sciences, 43(2):443—8, mar 2003.
Rong Long Wang, Zheng Tang, and Qi Ping Cao. An efficient approximation algorithm for finding a maximum clique using hopfield network learning. Neural Computation, 15(7):1605—19, jul 2003.
D. T Chiu, E. Pezzoli, H. Wu, A. D Stroock, and G. M. Whitesides. Using three-dimensional microfluidic networks for solving computationally hard problems. Proceedings of the National Academy of Sciences of the United States of America, 98(6):2961—6, mar 2001.
Ina Koch. Enumerating all connected maximal common subgraphs in two graphs. Theoretical Computer Science, 250(1-2):1—30, 2001.
Note: Transformation of the problem of finding all connected maximal common subgraphs into cliques. Adaptations of Bron-Kerbosch algorithm with pruning techniques to discard cliques that represent unconnected subgraphs.
Eleanor J. Gardiner, Peter Willett, and Peter J. Artymiuk. Graph-theoretic techniques for macromolecular docking. Journal of Chemical Information and Computer Sciences, 40(2):273—279, 2000.
Pavel A. Pevzner and Sing-Hoi Sze. Combinatorial approaches to finding subtle signals in dna sequences. In Russ Altman, Timothy L. Bailey, Philip Bourne, Michael Gribskov, Thomas Lengauer, Ilya N. Shindyalov, Lynn F. Ten Eyck, , and Helge Weissig, editors, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, volume 8, pages 269—278, 2000.
S. Bharitkar, K. Tsuchiya, and Y. Takefuji. Microcode optimization with neural networks. IEEE Transactions On Neural Networks / A Publication of the IEEE Neural Networks Council, 10(3):698—703, 1999.
M. D Miller, R. P Sheridan, and S. K. Kearsley. Sq: a program for rapidly producing pharmacophorically relevent molecular superpositions. Journal of Medicinal Chemistry, 42(9):1505—14, may 1999.
Ram Samudrala and John Moult. A graph-theoretic algorithm for comparative modeling of protein structure1. Journal of molecular biology, 279(1):287—302, 1998.
D. Bender and F. Losel. Protective and risk effects of peer relations and social support on antisocial behaviour in adolescents from multi-problem milieus. Journal of Adolescence, 20(6):661—78, dec 1997.
Eleanor J. Gardiner, Peter J. Artymiuk, and Peter Willett. Clique-detection algorithms for matching three-dimensional molecular structures. Journal of Molecular Graphics and Modelling, 15(4):245—253, 1997.
I. Hussain and T. R. Reed. A bond percolation-based model for image segmentation. IEEE Transactions On Image Processing, 6(12):1698—704, 1997.
P. D Kaplan, Q. Ouyang, D. S Thaler, and A. Libchaber. Parallel overlap assembly for the construction of computational dna libraries. Journal of Theoretical Biology, 188(3):333—41, oct 1997.
Filiberto Pla and John A. Marchant. Matching feature points in image sequences through a region-based method. Computer vision and image understanding, 66(3):271—285, 1997.
Ina Koch, Thomas Lengauer, and Egon Wanke. An algorithm for finding maximal common subtopologies in a set of protein structures. Journal of computational biology, 3(2):289—306, 1996.
Arun Jagota. Approximating maximum clique with a hopfield network. IEEE Transactions On Neural Networks / A Publication of the IEEE Neural Networks Council, 6(3):724—35, 1995.
Helen M. Grindley, Peter J. Artymiuk, David W. Rice, and Peter Willett. Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm. Journal of Molecular Biology, 229(3):707—721, 1993.
Radu Horaud and Thomas Skordas. Stereo correspondence through feature grouping and maximal cliques. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 11(11):1168—1180, 1989.
D. Chabardes, M. Gagnan-Brunette, M. Imbert-Teboul, O. Gontcharevskaia, M. Montegut, A. Clique, and F. Morel. Adenylate cyclase responsiveness to hormones in various portions of the human nephron. The Journal of Clinical Investigation, 65(2):439—48, feb 1980.
J. Gary Augustson and Jack Minker. An analysis of some graph theoretical cluster techniques. Journal of the ACM (JACM), 17(4):571—588, 1970.
Frank Harary and Ian C. Ross. A procedure for clique detection using the group matrix. Sociometry, 20(3):205—215, 1957.
R. Duncan Luce and Albert D. Perry. A method of matrix analysis of group structure. Psychometrika, 14(1):95—116, 1949.

1.4 Exact methods

1.4.1 Bron-Kerbosch and variants

David Eppstein and Darren Strash. Listing all maximal cliques in large sparse real-world graphs. In Panos Pardalos and Steffen Rebennack, editors, Experimental Algorithms, volume 6630 of Lecture Notes in Computer Science, pages 364—375. Springer Berlin / Heidelberg, 2011.
Note: Implementation of EppsteinLS:2010 and comparison with TomitaTT:2006 on several benchmarks of real, large, but very sparse graphs with low degenearcy number, or very small DIMACS instances.
David Eppstein, Marteen Löffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, Algorithms and Computation, volume 6506 of Lecture Notes in Computer Science, pages 403—414. Springer Berlin / Heidelberg, 2010.
Note: Variation of BronK:1973 with nodes ordered by degeneracy \(d\), which runs in \(O(dn3^{d/3})\). The algorithm can be applied to large graphs with low degeneracy number (see EppsteinS:2011).
Coen Bron and Joep Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Communications of ACM, 16(9):575—577, sep 1973.
Note: Exact algorithm very popular in computational chemistry and other application domains. Variants with special pivoting rules are among the best performing exact algorithms for the problem. Being complete, it can be applied only to very small instances or to larger instances with small degeneracy number (see EppsteinS:2011).

1.4.2 Other exact methods

Chu-Min Li, Zhiwen Fang, and Ke Xu. Combining maxsat reasoning and incremental upper bound for the maximum clique problem. In Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on, pages 939—946, nov 2013.
Ciaran McCreesh and Patrick Prosser. Multi-threading a state-of-the-art maximum clique algorithm. Algorithms, 6(4):618—635, 2013.
Jingen Xiang, Cong Guo, and Ashraf Aboulnaga. Scalable maximum clique computation using mapreduce. To appear
Chu-Min Li and Zhe Quan. An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem. In Maria Fox and David Poole, editors, Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press, 2010.
Chu-Min Li and Zhe Quan. Combining graph structure exploitation and propositional reasoning for the maximum clique problem. In 22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), volume 1, pages 344—351. IEEE Computer Society, 2010.
Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1):28—42, 2006.
Note: Theoretical work on worst case complexity of generating all maximal cliques with a depth-first search algorithm. The exact algorithm has a pruning methods that are similar to the Bron-Kerbosh algorithm (BronK:1973), and a different, more compact, representation of the enumerated maximal cliques. The algorithm has \(O(3^{n/3})\) worst-case time complexity for enumerating all maximal cliques (which is optimal).
Etsuji Tomita and Tomokazu Seki. An efficient branch-and-bound algorithm for finding a maximum clique. In Cristian Calude, Michael Dinneen, and Vincent Vajnovszki, editors, Discrete Mathematics and Theoretical Computer Science, volume 2731 of Lecture Notes in Computer Science, pages 278—289. Springer Berlin / Heidelberg, 2003.
Torsten Fahle. Simple and fast: Improving a branch-and-bound algorithm for maximum clique. In Rolf Möhring and Rajeev Raman, editors, Algorithms — ESA 2002, volume 2461 of Lecture Notes in Computer Science, pages 47—86. Springer Berlin / Heidelberg, 2002.
Patric R.J. Östergård. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1):197—207, 2002.
Yuji Shinano, Tetsuya Fujie, Yoshiko Ikebe, and Ryuichi Hirabayashi. Solving the maximum clique problem using pubb. In Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International… and Symposium on Parallel and Distributed Processing 1998, pages 326—332. IEEE, 1998.
David R. Wood. An algorithm for finding a maximum clique in a graph. Operations Research Letters, 21(5):211—217, 1997.
Randy Carraghan and Panos M. Pardalos. An exact algorithm for the maximum clique problem. Operations Research Letters, 9(6):375—382, 1990.
C. Friden, A. Hertz, and D. De Werra. Tabaris: an exact algorithm based on tabu search for finding a maximum independent set in a graph. Computers & Operations Research, 17(5):437—445, 1990. [Maximum Independent Set]
Egon Balas and Chang Sung Yu. Finding a maximum clique in an arbitrary graph. SIAM Journal on Computing, 15:1054, 1986.

1.5 Continuous formulations

Yuejian Peng and Cheng Zhao. A motzkin-straus type result for 3-uniform hypergraphs. Graphs and Combinatorics, pages 1—14, 2012.
Marcello Pelillo and Andrea Torsello. Payoff-monotonic game dynamics and the maximum clique problem. Neural Computation, 18(5):1215—58, may 2006.
Immanuel M. Bomze, Marco Budinich, Marcello Pelillo, and Claudio Rossi. Annealed replication: a new heuristic for the maximum clique problem. Discrete Applied Mathematics, 121(1-3):27—49, 2002.
Samuel Burer, Renato D.C. Monteiro, and Yin Zhang. Maximum stable set formulations and heuristics based on continuous optimization. Mathematical Programming, 94(1):137—166, 2002. [Maximum Independent Set]
Immanuel M. Bomze, Marcello Pelillo, and Robert Giacomini. Evolutionary approach to the maximum clique problem: Empirical evidence on a larger scale. In Immanuel M. Bomze, Tibor Csendes, Reiner Horst, and Panos M. Pardalos, editors, Developments in global optimization, volume 18, pages 95—108. Dordrecht, The Netherlands: Kluwer, 1997.
Luana E. Gibbons, Donald W. Hearn, Panos M. Pardalos, and Motakuri V. Ramana. Continuous characterizations of the maximum clique problem. Mathematics of Operations Research, 22(3):pp. 754—768, 1997.
Luana E. Gibbons, Donald W. Hearn, and Panos M. Pardalos. A continuous based heuristic for the maximum clique problem. Cliques Coloring and Satisfiability Second DIMACS Implementation Challenge, 26:103—124, 1996.
Marcello Pelillo. Relaxation labeling networks for the maximum clique problem. Journal of Artificial Neural Networks, 2(4):313—328, 1995.
Panos M. Pardalos and Andrew T. Phillips. A global optimization approach for solving the maximum clique problem. International Journal of Computer Mathematics, 33(3-4):209—216, 1990.

1.6 Instances

1.6.1DIMACS

Mark Brockington and Joseph C. Culberson. Camouflaging independent sets in quasi-random graphs. Cliques Coloring and Satisfiability Second DIMACS Implementation Challenge, 26:75—88, 1996.
Jeffrey C. Lagarias and Peter W. Shor. Keller’s cube-tiling conjecture is false in high dimensions. BAMS: Bulletin of the American Mathematical Society, 27(2):279—283, 1992.
David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, and Catherine Schevon. Optimization by simulated annealing: an experimental evaluation; part {II}, graph coloring and number partitioning. Operations Research, 39(3):378—406, may 1991.
K. Corrádi and S. Szabó. A combinatorial approach for keller’s conjecture. Periodica Mathematica Hungarica, 21(2):95—100, 1990.

2 Generalisations

2.1 Quasi-Cliques

2.1.1 Stochastic Local Search algorithms

Sanghamitra Bandyopadhyay and Malay Bhattacharyya. A neuro-ga approach for the maximum fuzzy clique problem. 5506:605—612, 2009
Mauro Brunato, Holger H. Hoos, and Roberto Battiti. On effectively finding maximal quasi-cliques in graphs. In Vittorio Maniezzo, Roberto Battiti, and Jean-Paul Watson, editors, Learning and Intelligent Optimization, Lecture Notes in Computer Science, pages 41—55. Springer-Verlag, Berlin, Heidelberg, 2008.
Note: New unifying formulation of quasi-cliques and adaptation of a reactive tabu search (BattitiM:2010) and a dynamic local search (PullanH:2006) for the problem.

2.1.2 Applications

Gaël Varoquaux, Alexandre Gramfort, Jean-Baptiste Poline, and Bertrand Thirion. Markov models for fmri correlation structure: Is brain functional connectivity small world, or decomposable into networks. In press [neuroscience - brain networks]

2.2 Weighted Maximum Clique

2.2.1 Surveys / Theory

Andreas Brandstädt and Vassilis Giakoumakis. Maximum weight independent sets in hole- and co-chair-free graphs. Information Processing Letters, 112(3):67—71, 2012. [Maximum Independent Set] Restriction to graph class having special properties.
Pedro Martins. Cliques with maximum/minimum edge neighborhood and neighborhood density. Computers and Operations Research, 39(3):594—608, 2012.
Nicolas Trotignon and Kristina Vušković. Combinatorial optimization with 2-joins. Journal of Combinatorial Theory. Series B, 102(1):153—185, 2012. Restriction to graph class having special properties.

2.2.2 Stochastic Local Search algorithms

Qinghua Wu, Jin-Kao Hao, and Fred Glover. Multi-neighborhood tabu search for the maximum weight clique problem. Annals of Operations Research, 196(1):611—634, 2012.
Wayne Pullan. Approximating the maximum vertex/edge weighted clique using local search. Journal of Heuristics, 14(2):117—134, 2007.

2.2.3 Applications

Xavier Delorme, Alexandre Dolgui, and Mikhail Y. Kovalyov. Combinatorial design of a minimum cost transfer line. Omega, 40(1):31—41, 2012. [assemply lines optimisation]
Franco Mascia, Elisa Cilia, Mauro Brunato, and Andrea Passerini. Predicting structural and functional sites in proteins by searching for maximum-weight cliques. In Maria Fox and David Poole, editors, Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press, 2010. [bioinformatics - proteomics - metal-binding site discovery - active site prediction - supervised clustering]
Note: Novel supervised clustering technique based on weighted maximum cliques, for collectively predicting all the residues belonging to the same protein functional site.
Massimiliano Pavan and Marcello Pelillo. Dominant sets and pairwise clustering. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 29(1):167—172, 2007. [clustering - computer vision - image segmentation]
Shidong Wang, Li Zheng, and Zhihai Zhang. Study on plan of track lines in marshalling station. In IEEM 2007: 2007 IEEE International Conference on Industrial Engineering and Engineering Management, pages 852—856, 2007. [planning of track lines, train schedules]

2.2.4 Exact methods

Egon Balas and J. Xue. Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs. SIAM Journal on Computing, 20:209, 1991.

2.2.5 Continuous formulations

Massimiliano Pavan and Marcello Pelillo. Dominant sets and pairwise clustering. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 29(1):167—172, 2007.
Stanislav Busygin. A new trust region technique for the maximum weight clique problem. Discrete Applied Mathematics, 154(15):2080—2096, 2006.
Alessio Massaro, Marcello Pelillo, and Immanuel M. Bomze. A complementary pivoting approach to the maximum weight clique problem. SIAM Journal on Optimization, 12(4):928—948, 2002.
Immanuel M. Bomze, Marcello Pelillo, and Volker Stix. Approximating the maximum weight clique using replicator dynamics. IEEE Transactions On Neural Networks / A Publication of the IEEE Neural Networks Council, 11(6):1228—41, 2000.
last update, 26 Oct 2015