Solving the Maximum Clique and Vertex Coloring Problems on Very Large Sparse Networks

References

• Abello J, Pardalos PM, Resende M (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, Providence, RI), 119–130.Crossref, Google Scholar
• Bader DA, Meyerhenke H, Sanders P, Wagner D, eds. (2013) Graph partitioning and graph clustering. 10th DIMACS Implementation Challenge Workshop, Atlanta, GA. Accessed November 20, 2014, http://www.cc.gatech.edu/dimacs10/.Crossref, Google Scholar
• Balas E, Xue J (1996) Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring. Algorithmica 15:397–412.Crossref, Google Scholar
• Battiti R, Protasi M (2001) Reactive local search for the maximum clique problem. Algorithmica 29:610–637.Crossref, Google Scholar
• Bianconi G, Marsili M (2006) Emergence of large cliques in random scale-free networks. Europhysics Lett. 74:740–746.Crossref, Google Scholar
• Bollobás B, Thomason A (1985) Random graphs of small order. Ann. Discrete Math. 28:47–97.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, The Netherlands), 1–74.Crossref, Google Scholar
• Brélaz D (1979) New methods to color the vertices of a graph. Commun. ACM 22:251–256.Crossref, Google Scholar
• Buchanan A, Walteros JL, Butenko S, Pardalos PM (2014) Solving maximum clique in sparse graphs: An O(nm + n2d/4) algorithm for d-degenerate graphs. Optim. Lett. 8:1611–1617.Crossref, Google Scholar
• Butenko S, Trukhanov S (2007) Using critical sets to solve the maximum independent set problem. Oper. Res. Lett. 35:519–524.Crossref, Google Scholar
• Butenko S, Wilhelm WE (2006) Clique-detection models in computational biochemistry and genomics. Eur. J. Oper. Res. 173:1–17.Crossref, Google Scholar
• Campêlo M, Campos VA, Corrêa RC (2008) On the asymmetric representatives formulation for the vertex coloring problem. Discrete Appl. Math. 156:1097–1111.Crossref, Google Scholar
• Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9:375–382.Crossref, Google Scholar
• Cheng J, Ke Y, Fu AWC, Yu JX, Zhu L (2011) Finding maximal cliques in massive networks. ACM Trans. Database Syst. 36(4):21:1–21:34.Crossref, Google Scholar
• Cohen JD (2008) Trusses: Cohesive subgraphs for social network analysis. Technical report, National Security Agency, Fort Meade, MD.Google Scholar
• Corno F, Prinetto P, Sonza Reorda M (1995) Using symbolic techniques to find the maximum clique in very large sparse graphs. Proc. 1995 Eur. Conf. Design and Test, EDTC’95 (IEEE Computer Society, Washington, DC), 320–324Crossref, Google Scholar
• Culberson JC (1996) Culberson’s Graph Coloring Programs. Accessed November 20, 2014, http://webdocs.cs.ualberta.ca/~joe/Coloring/Colorsrc/index.html.Google Scholar
• Culberson JC, Luo F (1996) Exploring the k-colorable landscape with iterated greedy. Johnson DS, Trick MA, eds. Cliques, Coloring, and Satisfiability, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, Vol. 26 (American Mathematical Society, Providence, RI), 245–284.Crossref, Google Scholar
• Eppstein D, Strash D (2011) Listing all maximal cliques in large sparse real-world graphs. Pardalos P, Rebennack S, eds. Experimental Algorithms, Lecture Notes in Computer Science, Vol. 6630 (Springer, Berlin), 364–375.Crossref, Google Scholar
• Feige U, Kilian J (1998) Zero knowledge and the chromatic number. J. Comput. System Sci. 57:187–199.Crossref, Google Scholar
• Gendreau M, Soriano P, Salvail L (1993) Solving the maximum clique problem using a tabu search approach. Ann. Oper. Res. 41:385–403.Crossref, Google Scholar
• Gualandi S, Malucelli F (2012) Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24:81–100.Link, Google Scholar
• Hansen P, Labbé M, Schindl D (2009) Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results. Discrete Optim. 6:135–147.Crossref, Google Scholar
• Håstad J (1999) Clique is hard to approximate within n1−ϵ. Acta Mathematica 182:105–142.Crossref, Google Scholar
• Held S, Cook W, Sewell E (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4:363–381.Crossref, Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, eds. Complexity of Computer Computations (Plenum, New York), 85–103.Crossref, Google Scholar
• Katayama K, Hamamoto A, Narihisa H (2005) An effective local search for the maximum clique problem. Inform. Processing Lett. 95:503–511.Crossref, Google Scholar
• Leskovec J, Krevl A (2014) SNAP Datasets: Stanford Large Network Dataset Collection. Accessed November 20, 2014, http://snap.stanford.edu/data.Google Scholar
• Lick DR, White AT (1970) k-degenerate graphs. Canad. J. Math. 22:1082–1096.Crossref, Google Scholar
• Lu L, Gu Y, Grossman R (2010) dMaximalCliques: A distributed algorithm for enumerating all maximal cliques and maximal clique distribution. Fan W, Hsu W, Webb GI, Liu B, Zhang C, Gunopulos D, Wu X, eds. IEEE Internat. Conf. Data Mining Workshops (ICDMW) (IEEE Computer Society, Washington, DC), 1320–1327.Crossref, Google Scholar
• Malaguti E, Toth P (2010) A survey on vertex coloring problems. Internat. Transactions Oper. Res. 17:1–34.Crossref, Google Scholar
• Malaguti E, Monaci M, Toth P (2011) An exact approach for the vertex coloring problem. Discrete Optim. 8:174–190.Crossref, Google Scholar
• Matula DW, Beck LL (1983) Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30:417–427.Crossref, Google Scholar
• Mehrotra A, Trick MA (1996) A column generation approach for graph coloring. INFORMS J. Comput. 8:344–354.Link, Google Scholar
• Méndez-Díaz I, Zabala P (2006) A branch-and-cut algorithm for graph coloring. Discrete Appl. Math. 154:826–847.Crossref, Google Scholar
• Modani N, Dey K, Mukherjea S, Nanavati AA (2010) Discovery and analysis of tightly knit communities in telecom social networks. IBM J. Res. Development 54:7:1–7:13.Crossref, Google Scholar
• Morgenstern C (1996) Distributed coloration neighborhood search. Johnson DS, Trick MA, eds. Cliques, Coloring, and Satisfiability, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, Vol. 26 (American Mathematical Society, Providence, RI), 335–358.Crossref, Google Scholar
• Newman M (2003) The structure and function of complex networks. SIAM Rev. 45:167–256.Crossref, Google Scholar
• Östergård PRJ (2002) A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120:197–207.Crossref, Google Scholar
• Pardalos PM, Mavridou T, Xue J (1998) The graph coloring problem: A bibliographic survey. Du D-Z, Pardalos PM, eds. Handbook of Combinatorial Optimization, Vol. 2 (Kluwer Academic Publishers, Dordrecht, The Netherlands), 331–395.Crossref, Google Scholar
• Shen Y, Nguyen DT, Xuan Y, Thai MT (2012) New techniques for approximating optimal substructure problems in power-law graphs. Theoret. Comput. Sci. 447:107–119.Crossref, Google Scholar
• Sloane NJA (2011) Challenge Problems: Independent Sets in Graphs. Accessed November 20, 2014, http://neilsloane.com/doc/graphs.html.Google Scholar
• Szekeres G, Wilf HS (1968) An inequality for the chromatic number of a graph. J. Combin. Theory 4:1–3.Crossref, Google Scholar
• Tomita E, Seki T (2003) An efficient branch-and-bound algorithm for finding a maximum clique. Calude C, Dinneen M, Vajnovszki V, eds. Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 2731 (Springer, Berlin), 278–289.Crossref, Google Scholar
• Wood DR (1997) An algorithm for finding a maximum clique in a graph. Oper. Res. Lett. 21:211–217.Crossref, Google Scholar
• Zuckerman D (2007) Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3:103–128.Crossref, Google Scholar