On the 2-Club Polytope of Graphs

References

• Aardal K, van Hoesel S (1996) Polyhedral techniques in combinatorial optimization I: Theory. Statistica Neerlandica 50(3):3–26.Crossref, Google Scholar
• Alba RD (1973) A graph-theoretic definition of a sociometric clique. J. Math. Sociology 3(1):113–126.Crossref, Google Scholar
• Almeida MT, Carvalho FD (2012) Integer models and upper bounds for the 3-club problem. Networks 60(3):155–166.Crossref, Google Scholar
• Almeida MT, Carvalho FD (2014) An analytical comparison of the LP relaxations of integer models for the k-club problem. Eur. J. Oper. Res. 232(3):489–498.Crossref, Google Scholar
• Asahiro Y, Miyano E, Samizo K (2010) Approximating maximum diameter-bounded subgraphs. Lopez-Ortiz A, ed. LATIN 2010: Theoretical Informatics, Lecture Notes in Computer Science, Vol. 6034 (Springer, Berlin), 615–626.Crossref, Google Scholar
• Bader GD, Hogue CWV (2003) An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics 4:2.Crossref, Google Scholar
• Bader JS, Chaudhuri A, Rothberg JM, Chant J (2004) Gaining confidence in high-throughput protein interaction networks. Nature Biotechnology 22(1):78–85.Crossref, Google Scholar
• Balas E, Jeroslow R (1972) Canonical cuts on the unit hypercube. SIAM J. Appl. Math. 23(1):61–69.Crossref, Google Scholar
• Balasundaram B (2007) Graph theoretic generalizations of clique: Optimization and extensions. Unpublished doctoral dissertation, Texas A&M University, College Station.Google Scholar
• Balasundaram B, Mahdavi Pajouh F (2013) Graph theoretic clique relaxations and applications. Pardalos PM, Du D-Z, Graham R, eds. Handbook of Combinatorial Optimization, 2nd ed. (Springer, New York), 1559–1598.Crossref, Google Scholar
• Balasundaram B, Butenko S, Trukhanov S (2005) Novel approaches for analyzing biological networks. J. Combinatorial Optim. 10(1):23–39.Crossref, Google Scholar
• Boginski V (2011) Network-based data mining: Operations research techniques and applications. Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Hoboken, NJ), 3498–3508.Crossref, Google Scholar
• Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximum clique problem. Du D-Z, Pardalos PM, eds. Handbook of Combinatorial Optimization (Kluwer Academic Publishers, Dordrecht, The Netherlands), 1–74.Crossref, Google Scholar
• Bourjolly J-M, Laporte G, Pesant G (2000) Heuristics for finding k-clubs in an undirected graph. Comput. Oper. Res. 27(6):559–569.Crossref, Google Scholar
• Bourjolly J-M, Laporte G, Pesant G (2002) An exact algorithm for the maximum k-club problem in an undirected graph. Eur. J. Oper. Res. 138(1):21–28.Crossref, Google Scholar
• Carvalho FD, Almeida MT (2011) Upper bounds and heuristics for the 2-club problem. Eur. J. Oper. Res. 210(3):489–494.Crossref, Google Scholar
• Chang M-S, Hung L-J, Lin C-R, Su P-C (2013) Finding large k-clubs in undirected graphs. Computing 95(9):739–758.Crossref, Google Scholar
• Cook DJ, Holder LB (2000) Graph-based data mining. IEEE Intelligent Systems 15(2):32–41.Crossref, Google Scholar
• Dimacs (2012) Graph partitioning and graph clustering: Tenth Dimacs implementation challenge. Accessed February 2015, http://www.cc.gatech.edu/dimacs10/index.shtml.Google Scholar
• Downey RG, Fellows MR (1995) Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoret. Comput. Sci. 141(1–2):109–131.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
• Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12):7821–7826.Crossref, Google Scholar
• Gurobi Optimization, Inc. (2015) Gurobi optimizer reference manual. http://www.gurobi.com.Google Scholar
• Harary F, Ross IC (1957) A procedure for clique detection using the group matrix. Sociometry 20(3):205–215.Crossref, Google Scholar
• Hartung S, Komusiewicz C, Nichterlein A (2015) Parameterized algorithmics and computational experiments for finding 2-clubs. J. Graph Algorithms Appl. 19(1):155–190.Crossref, Google Scholar
• Håstad J (1999) Clique is hard to approximate within n1−ɛ. Acta Mathematica 182(1):105–142.Crossref, Google Scholar
• Hill S, Provost F, Volinsky C (2006) Network-based marketing: Identifying likely adopters via consumer networks. Statist. Sci. 21(2):256–276.Crossref, Google Scholar
• Iacobucci D, Hopkins N (1992) Modelling dyadic interactions and networks in marketing. J. Marketing Res. 29(1):5–17.Crossref, Google Scholar
• Liu H, Zhang P, Zhu D (2012) On editing graphs into 2-club clusters. Snoeyink J, Lu P, Su K, Wang L, eds. Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science, Vol. 7285 (Springer, Berlin), 235–246.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
• Mahdavi Pajouh F, Balasundaram B (2012) On inclusionwise maximal and maximum cardinality k-clubs in graphs. Discrete Optim. 9(2):84–97.Crossref, Google Scholar
• McClosky B (2011) Clique relaxations. Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science, Vol. 1 (John Wiley & Sons, Hoboken, NJ), 650–657.Crossref, Google Scholar
• Miao J, Berleant D (2004) From paragraph networks to document networks. Proc. Internat. Conf. Inform. Tech.: Coding Comput., ITCC ’04, Vol. 1 (IEEE, Piscataway, NJ), 295–302.Google Scholar
• Misra N, Panolan F, Saurabh S (2013) Subexponential algorithm for d-cluster edge deletion: Exception or rule? Chatterjee K, Sgall J, eds. Mathematical Foundations of Computer Science 2013, Lecture Notes in Computer Science, Vol. 8087 (Springer, Berlin), 679–690.Crossref, Google Scholar
• Mokken RJ (1979) Cliques, clubs and clans. Quality and Quantity 13(2): 161–173.Crossref, Google Scholar
• Moradi E, Balasundaram B (2015) Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts. Optim. Lett. DOI: 10.1007/s11590-015-0971-7.Crossref, Google Scholar
• Nemhauser GL, Trotter LE (1974) Properties of vertex packings and independence system polyhedra. Math. Programming 6(1):48–61.Crossref, Google Scholar
• Nemhauser GL, Trotter LE (1975) Vertex packing: Structural properties and algorithms. Math. Programming 8(1):232–248.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA (1999) Integer and Combinatorial Optimization (Wiley, New York).Google Scholar
• Padberg MW (1973) On the facial structure of set packing polyhedra. Math. Programming 5(1):199–215.Crossref, Google Scholar
• Pasupuleti S (2008) Detection of protein complexes in protein interaction networks using n-clubs. EvoBIO 2008: Proc. 6th Eur. Conf. Evolutionary Comput., Machine Learn. Data Mining in Bioinformatics, Lecture Notes in Computer Science, Vol. 4973 (Springer, Berlin), 153–164.Crossref, Google Scholar
• Pattillo J, Youssef N, Butenko S (2012) Clique relaxation models in social network analysis. Thai MT, Pardalos PM, eds. Handbook of Optimization in Complex Networks, Springer Optimization and Its Applications, Vol. 58 (Springer, New York), 143–162.Crossref, Google Scholar
• Pattillo J, Youssef N, Butenko S (2013) On clique relaxation models in network analysis. Eur. J. Oper. Res. 226(1):9–18.Crossref, Google Scholar
• Schäfer A, Komusiewicz C, Moser H, Niedermeier R (2012) Parameterized computational complexity of finding small-diameter subgraphs. Optim. Lett. 6(5):883–891.Crossref, Google Scholar
• Scott J (2000) Social Network Analysis: A Handbook, 2nd ed. (Sage Publications, London).Google Scholar
• Shahinpour S, Butenko S (2013a) Algorithms for the maximum k-club problem in graphs. J. Combinatorial Optim. 26(3):520–554.Crossref, Google Scholar
• Shahinpour S, Butenko S (2013b) Distance-based clique relaxations in networks: s-clique and s-club. Goldengorin BI, Kalyagin VA, Pardalos PM, eds. Models, Algorithms, and Technologies for Network Analysis, Vol. 59 (Springer, New York), 149–174.Crossref, Google Scholar
• Sparrow MK (1991) The application of network analysis to criminal intelligence: An assessment of the prospects. Soc. Networks 13(3): 251–274.Crossref, Google Scholar
• Spirin V, Mirny LA (2003) Protein complexes and functional modules in molecular networks. Proc. Natl. Acad. Sci. 100(21):12123–12128.Crossref, Google Scholar
• Terveen L, Hill W, Amento B (1999) Constructing, organizing, and visualizing collections of topically related, web resources. ACM Trans. Comput.-Human Interaction 6(1):67–94.Crossref, Google Scholar
• Trotter LE (1975) A class of facet producing graphs for vertex packing polyhedra. Discrete Math. 12(4):373–388.Crossref, Google Scholar
• U.S. Congress Office of Technology Assessment (1995) Technologies for detecting money laundering. Information Technologies for the Control of Money Laundering (U.S. Government Printing Office, Washington, DC), 51–74.Google Scholar
• Veremyev A, Boginski V (2012) Identifying large robust network clusters via new compact formulations of maximum k-club problems. Eur. J. Oper. Res. 218(2):316–326.Crossref, Google Scholar
• Veremyev A, Prokopyev OA, Pasiliao EL (2015) Critical nodes for distance-based connectivity and related problems in graphs. Networks 66(3):170–195.Crossref, Google Scholar
• Woodside AG, DeLozier MW (1976) Effects of word of mouth advertising on consumer risk taking. J. Advertising 5(4):12–19.Crossref, Google Scholar