×

Finding large \(k\)-clubs in undirected graphs. (English) Zbl 1310.05195

A \(k\)-club is a maximal set of vertices of a graph that induces a subgraph of diameter \(k\). Related concepts are \(k\)-clique and \(k\)-clan, see J.-M. Bourjolly et al. [Comput. Oper. Res. 27, No. 6, 559–569 (2000; Zbl 0955.91051); Eur. J. Oper. Res. 138, No. 1, 21–28 (2002; Zbl 1008.90048)]. This paper presents a branch-and-bound algorithm computing a maximum \(k\)-club in time \(O^\ast(1.62^n)\), and a heuristic for the same problem.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
90B10 Deterministic network models in operations research

Software:

DIMACS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alba RD (1973) A graph-theoretic definition of a sociometric clique. J Math Sociol 3:113-126 · Zbl 0297.92019 · doi:10.1080/0022250X.1973.9989826
[2] Almeida MT, Carvalho FD (2012) Integer models and upper bounds for the 3-club problem. Networks 60:155-166 · Zbl 1269.90120 · doi:10.1002/net.21455
[3] Asahiro Y, Miyano E, Samizo K (2010) Approximating maximum diameter-bounded subgraphs. In: Proceedings of LATIN. LNCS 6034:615-626 · Zbl 1283.05254
[4] Balasundaram B, Butenko S, Trukhanov S (2005) Novel approaches for analyzing biological networks. J Combinatorial Optim 10:23-39 · Zbl 1080.90010 · doi:10.1007/s10878-005-1857-x
[5] Batagelj V (2012) Network/Pajek Graph Files. http://vlado.fmf.uni-lj.si/pub/networks/pajek/data/gphs.htm · Zbl 1269.90120
[6] Bourjolly J-M, Laporte G, Pesant G (2000) Heuristics for finding \[k\]-clubs in an undirected graph. Comput Oper Res 27:559-569 · Zbl 0955.91051 · doi:10.1016/S0305-0548(99)00047-7
[7] Bourjolly J-M, Laporte G, Pesant G (2002) An exact algorithm for maximum \[k\]-club problem in an undirected graph. Eur J Oper Res 138:21-28 · Zbl 1008.90048 · doi:10.1016/S0377-2217(01)00133-3
[8] Carvalho FD, Almeida MT (2011) Upper bounds and heuristics for the 2-club problem. Eur J Oper Res 210:489-494 · Zbl 1213.90250 · doi:10.1016/j.ejor.2010.11.023
[9] Demetrescu C, Italiano GF (2004) A new approach to dynamic all pairs shortest paths. J ACM 51: 968-992 · Zbl 1125.68393
[10] DIMACS (1995) Maximum clique, graph coloring, and satisfiability. Second DIMACS implementation challenge http://dimacs.rutgers.edu/Challenges/ · Zbl 1008.90048
[11] Everitt B (1980) Cluster analysis. Halsted Press, New York · Zbl 0507.62060
[12] Flake GW, Tarjan RE, Tsioutsiouliklis KT (2004) Graph clustering and minimum cut trees. Internet Math 1:385-408 · Zbl 1098.68095 · doi:10.1080/15427951.2004.10129093
[13] Fomin FV, Grandoni F, Kratsch D (2009) A measure and conquer approach for the analysis of exact algorithms. J ACM 56(5):25 · Zbl 1325.68311 · doi:10.1145/1552285.1552286
[14] Franciosa PG, Frigioni D, Giaccio R (1997) Semi-dynamic shortest paths and breadth-first search in digraphs. In: Proceedings symposiunm on theoretical aspects of computer science (STACS 97). LNCS vol 1200:33-46 · Zbl 1498.68089
[15] Frigioni D, Marchetti-Spaccamela A, Nanni U (2000) Fully dynamic algorithms for maintaining shortest paths trees. J Algorithms 34:251-281 · Zbl 0949.68169 · doi:10.1006/jagm.1999.1048
[16] Gendreau M, Soriano P, Salvail L (1993) Solving the maximum clique problem using a tabu search approach. Ann Oper Res 41:385-403 · Zbl 0775.90297 · doi:10.1007/BF02023002
[17] Grossman J, Ion P, de Castro R (2012) The Erdős number project. http://www.oakland.edu/enp · Zbl 0297.92019
[18] Hartung S, Komusiewicz C, Nichterlein A (2012) Parameterized algorithmics and computational experiments for finding 2-clubs. In: Proceedings of IPEC. LNCS 7535:231-241 · Zbl 1375.68065
[19] Jain AK, Dubes RC (1988) Algorithms for clustering data. Prentice-Hall, Englewood Cliffs · Zbl 0665.62061
[20] Kannan R, Vempala S, Vetta A (2004) On clusterings-good, bad and spectral. J ACM 51:497-515 · Zbl 1192.05160 · doi:10.1145/990308.990313
[21] King V (1999) Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraph. In: Proceedings of FOCS, pp 81-91 · Zbl 1254.90279
[22] Kuan ST, Wu BY, Lee WJ (2008) Finding friend groups in Blogsphere. In: Proceedings of 22nd international conference on advanced information networking and application, pp 1046-1050 · Zbl 1269.90120
[23] Luce R (1950) Connectivity and generalized cliques in sociomatric group structure. Psychometrika 15:169-190 · doi:10.1007/BF02289199
[24] Mahdavi Pajouh F, Balasundaram B (2012) On inclusionwise maximal and maximum cardinality \[k\]-clubs in graphs. Discrete Optim 9:84-97 · Zbl 1246.90130 · doi:10.1016/j.disopt.2012.02.002
[25] Mokken RJ (1979) Cliques, clubs, and clans. Qual Quant 13:161-173 · doi:10.1007/BF00139635
[26] Schäfer A, Komusiewicz C, Moser H, Niedermeier R (2012) Parameterized computational complexity of finding small-diameter subgraphs. Optim Lett 6:883-891 · Zbl 1254.90279 · doi:10.1007/s11590-011-0311-5
[27] Scott J (2000) Social network analysis: a handbook. Sage Publication, London
[28] Shahinpour S, Butenko S (2012) Algorithms for the maximum \[k\]-club problem in graphs. J Combinatorial Optim. doi:10.1007/s10878-012-9473-z · Zbl 1282.90220
[29] Veremyev A, Boginski V (2012) Identifying large robust network clusters via new compact formulations of maximum \[k\]-club problems. Eur J Oper Res 218:316-326 · Zbl 1244.90201
[30] Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge University Press, Cambridge · Zbl 0926.91066
[31] Yang C-P, Chen H-C, Hsiea S-D, Wu BY (2009) Heuristic algorithms for finding 2-club in an undirected graph. In: Proceedings of NCS workshop on algorithms and bioinformatics, pp 176-181
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.