An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph

References

• Abello J, Pardalos PM, Resende MGC (1999) On maximum clique problems in very large graphs. Abello J, Vitter J, eds. External Memory Algorithms and Visualization, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 50 (American Mathematical Society, Boston), 119–130.Crossref, Google Scholar
• Abello J, Resende MGC, Sudarsky S (2002) Massive quasi-clique detection. Rajsbaum S, ed. LATIN 2002: Proc. 5th Latin Amer. Sympos. Theor. Informatics (Springer-Verlag, London), 598–612.Google Scholar
• Alba RD (1973) A graph-theoretic definition of a sociometric clique. J. Math. Sociol. 3(1):113–126.Crossref, Google Scholar
• Balasundaram B, Butenko S, Hicks IV (2011) Clique relaxations in social network analysis: The maximum k-plex problem. Oper. Res. 59(1):133–142.Link, Google Scholar
• Balasundaram B, Butenko S, Trukhanov S (2005) Novel approaches for analyzing biological networks. J. Combin. Optim. 10(1):23–39.Crossref, Google Scholar
• Bazaraa MS, Sherali HD, Shetty CM (2006) Nonlinear Programming: Theory And Algorithms, 3rd ed. (Wiley-Interscience, New York).Crossref, Google Scholar
• Boginski V, Butenko S, Pardalos P (2006) Mining market data: A network approach. Comput. Oper. Res. 33(11):3171–3184.Crossref, Google Scholar
• Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximum clique problem. Du DZ, Pardalos PM, eds. Handbook of Combinatorial Optimization (Kluwer Academic Publishers, Dordrecht, Netherlands), 1–74.Crossref, Google Scholar
• Boros E, Hammer PL, Tavares G (2007) Local search heuristics for quadratic unconstrained binary optimization. J. Heuristics 13(2):99–132.Crossref, Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bu D, Zhao Y, Cai L, Xue H, Zhu X, Lu H, Zhang J, et al.. (2003) Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Res. 31(9):2443–2450.Crossref, Google Scholar
• Butenko S, Wilhelm W (2006) Clique-detection models in computational biochemistry and genomics. Eur. J. Oper. Res. 173:1–17.Crossref, Google Scholar
• Carraghan R, Pardalos P (1990) An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6):375–382.Crossref, Google Scholar
• Corneil D, Perl Y (1984) Clustering and domination in perfect graphs. Discrete Appl. Math. 9(1):27–39.Crossref, Google Scholar
• Davis TA, Hu Y (2011) The University of Florida sparse matrix collection. ACM Trans. Math. Software 38(1):1–25.Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Feige U, Kortsarz G, Peleg D (2001) The dense k-subgraph problem. Algorithmica 29:410–421.Crossref, Google Scholar
• Freeman LC (1992) The sociological concept of “group”: An empirical test of two models. Amer. J. Sociol. 98(1):152–166.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, New York).Google Scholar
• Golub GH, Van Loan CF (1996) Matrix Computations, 3rd ed. (Johns Hopkins University Press, Baltimore).Google Scholar
• Gurobi Optimization LLC (2018) Gurobi optimizer reference manual. Accessed August 1, 2019. https://www.gurobi.com/documentation/8.1/refman/index.html.Google Scholar
• Harary F, Ross IC (1957) A procedure for clique detection using the group matrix. Sociometry 20(3):205–215.Crossref, Google Scholar
• Huang TW, Lin CY, Kao CY (2007) Reconstruction of human protein interolog network using evolutionary conserved network. BMC Bioinformatics 8(1):152.Crossref, Google Scholar
• Intel Corporation (2019) Intel math kernel library. Accessed August 1, 2019. https://software.intel.com/en-us/mkl.Google Scholar
• Johnson D, Trick M, eds. (1996) Cliques, Coloring, and Satisfiability: Second Dimacs Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26 (American Mathematical Society, Providence, RI).Google Scholar
• Kortsarz G, Peleg D (1993) On choosing a dense subgraph. Proc. 34th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 692–701.Google Scholar
• Li D, Sun X, Liu C (2012) An exact solution method for unconstrained quadratic 0–1 programming: A geometric approach. J. Global Optim. 52(4):797–829.Crossref, Google Scholar
• Lu H, Zhu X, Liu H, Skogerbø G, Zhang J, Zhang Y, Cai L, et al.. (2004) The interactome as a tree—An attempt to visualize the protein-protein interaction network in yeast. Nucleic Acids Res. 32(16):4804–4811.Crossref, Google Scholar
• Luce RD (1950) Connectivity and generalized cliques in sociometric group structure. Psychometrika 15(2):169–190.Crossref, Google Scholar
• Luce RD, Perry AD (1949) A method of matrix analysis of group structure. Psychometrika 14(2):95–116.Crossref, Google Scholar
• McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Programming 10(1):147–175.Crossref, Google Scholar
• Miao Z (2016) Combinatorial and global optimization approaches to the maximum quasi-clique problem. Unpublished doctoral thesis, Oklahoma State University, Stillwater, Oklahoma.Google Scholar
• Mokken RJ (1979) Cliques, clubs and clans. Quality Quantity 13(2):161–173.Crossref, Google Scholar
• Östergård PRJ (2002) A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120(1–3):197–207.Crossref, Google Scholar
• Pajouh FM, Miao Z, Balasundaram B (2014) A branch-and-bound approach for maximum quasi-cliques. Ann. Oper. Res. 216(1):145–161.Crossref, Google Scholar
• Pan VY, Chen ZQ (1999) The complexity of the matrix eigenproblem. Proc. 31st Annual ACM Sympos. Theory Comput. STOC ’99 (ACM, New York), 507–516.Google Scholar
• Pardalos PM, Jha S (1992) Complexity of uniqueness and local search in quadratic 0–1 programming. Oper. Res. Lett. 11(2):119–123.Crossref, Google Scholar
• Pardalos PM, Xue J (1994) The maximum clique problem. J. Global Optim. 4(3):301–328.Crossref, Google Scholar
• Pattillo J, Youssef N, Butenko S (2013b) On clique relaxation models in network analysis. Eur. J. Oper. Res. 226(1):9–18.Crossref, Google Scholar
• Pattillo J, Veremyev A, Butenko S, Boginski V (2013a) On the maximum quasi-clique problem. Discrete Appl. Math. 161(1–2):244–257.Crossref, Google Scholar
• Pinto BQ, Ribeiro CC, Rosseti I, Plastino A (2018) A biased random-key genetic algorithm for the maximum quasi-clique problem. Eur. J. Oper. Res. 271(3):849–865.Crossref, Google Scholar
• Saban D, Bonomo F, Stier-Moses NE (2010) Analysis and models of bilateral investment treaties using a social networks approach. Physica A: Statist. Mech. Appl. 389(17):3661–3673.Crossref, Google Scholar
• Seidman SB, Foster BL (1978) A graph theoretic generalization of the clique concept. J. Math. Sociol. 6(1):139–154.Crossref, Google Scholar
• Strang G (1988) Linear Algebra and Its Applications (Harcourt Brace Jovanovich College Publishers, San Diego).Google Scholar
• Trukhanov S, Balasubramaniam C, Balasundaram B, Butenko S (2013) Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations. Comput. Optim. Appl. 56(1):113–130.Crossref, Google Scholar
• Uno T (2010) An efficient algorithm for solving pseudo clique enumeration problem. Algorithmica 56(1):3–16.Crossref, Google Scholar
• Veremyev A, Prokopyev OA, Butenko S, Pasiliao EL (2016) Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs. Comput. Optim. Appl. 64(1):177–214.Crossref, Google Scholar
• Wasserman S, Faust K (1994) Social Network Analysis (Cambridge University Press, New York).Crossref, Google Scholar
• Yang X, Zola J, Aluru S (2011) Parallel metagenomic sequence clustering via sketching and maximal quasi-clique enumeration on map-reduce clouds. 2011 IEEE Internat. Parallel Distributed Processing Sympos. (IPDPS) (IEEE, Piscataway, NJ), 1223–1233.Google Scholar