Partitioning a Graph into Low-Diameter Clusters

References

• Abbasi AA, Younis M (2007) A survey on clustering algorithms for wireless sensor networks. Comput. Comm. 30(14–15):2826–2841.Crossref, Google Scholar
• Abello J, Resende MG, Sudarsky S (2002) Massive quasi-clique detection. LATIN 2002: Theoret. Informatics: 5th Latin Amer. Sympos. Cancun, Mexico, April 3–6, 2002 Proc. 5 (Springer), 598–612.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
• 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. Comb. Optim. 10:23–39.Crossref, Google Scholar
• Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512.Crossref, Google Scholar
• Ben-David S (2015) Computational feasibility of clustering under clusterability assumptions. Preprint, submitted January 2, https://arxiv.org/abs/1501.00437.Google Scholar
• Bourjolly JM, 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
• Bron C, Kerbosch J (1973) Algorithm 457: Finding all cliques of an undirected graph. Comm. ACM 16(9):575–577.Crossref, Google Scholar
• Daniely A, Linial N, Saks M (2012) Clustering is difficult only when it does not matter. Preprint, submitted May 22, https://arxiv.org/abs/1205.4891.Google Scholar
• Deogun JS, Kratsch D, Steiner G (1997) An approximation algorithm for clustering graphs with dominating diametral path. Inform. Processing Lett. 61(3):121–127.Crossref, Google Scholar
• Desormeaux WJ, Haynes TW, Henning MA, Yeo A (2014) Total domination in graphs with diameter 2. J. Graph Theory 75(1):91–103.Crossref, Google Scholar
• Dondi R, Mauri G, Sikora F, Zoppis I (2019) Covering a graph with clubs. J. Graph Algorithms Appl. 23(2):271–292.Crossref, Google Scholar
• Eisen MB, Spellman PT, Brown PO, Botstein D (1998) Cluster analysis and display of genome-wide expression patterns. Proc. Natl. Acad. Sci. USA 95(25):14863–14868.Crossref, Google Scholar
• Eppstein D, Löffler M, Strash D (2013) Listing all maximal cliques in large sparse real-world graphs. ACM J. Experiment. Algorithmics 18(3):3.1–3.21.Google Scholar
• Erdős P, Rényi A (1960) On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5(1):17–60.Google Scholar
• Fernandess Y, Malkhi D (2002) k-clustering in wireless ad hoc networks. Proc. Second ACM Internat. Workshop Principles Mobile Comput., 31–37.Google Scholar
• Gschwind T, Irnich S, Furini F, Calvo RW (2021) A branch-and-price framework for decomposing graphs into relaxed cliques. INFORMS J. Comput. 33(3):1070–1090.Link, Google Scholar
• Hagberg A, Swart PJ, Schult DA (2008a) Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM.Google Scholar
• Hagberg AA, Schult DA, Swart PJ (2008b) Exploring network structure, dynamics, and function using NetworkX. Varoquaux G, Vaught T, Millman J, eds. Proc. 7th Python Sci. Conf., 11–15.Google Scholar
• Johnson DS (1974) Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9(3):256–278.Crossref, Google Scholar
• Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys. Rev. E. 78(4):046110.Crossref, Google Scholar
• Lu Y, Salemi H, Balasundaram B, Buchanan A (2022) On fault-tolerant low-diameter clusters in graphs. INFORMS J. Comput. 34(6):3181–3199.Link, Google Scholar
• Luce RD (1950) Connectivity and generalized cliques in sociometric group structure. Psychometrika 15(2):169–190.Crossref, Google Scholar
• Lund C, Yannakakis M (1994) On the hardness of approximating minimization problems. J. ACM 41(5):960–981.Crossref, Google Scholar
• Miller RE, Muller DE (1960) A problem of maximum consistent subsets. Technical report, IBM Research Report RC-240, JT Watson Research Center, Yorktown Heights, NY.Google Scholar
• Mokken RJ (1979) Cliques, clubs and clans. Quality Quantity 13(2):161–173.Crossref, Google Scholar
• Moon JW, Moser L (1965) On cliques in graphs. Israel J. Math. 3:23–28.Crossref, Google Scholar
• Newman M, Barabási AL, Watts DJ (2006) The Structure and Dynamics of Networks, vol. 12 (Princeton University Press, Princeton, NJ).Google Scholar
• Pattillo J, Youssef N, Butenko S (2013a) 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 (2013b) On the maximum quasi-clique problem. Discrete Appl. Math. 161(1–2):244–257.Crossref, Google Scholar
• Rochat L, Bianchi-Demicheli F, Aboujaoude E, Khazaal Y (2019) The psychology of “swiping”: A cluster analysis of the mobile dating app Tinder. J. Behav. Addictions 8(4):804–813.Crossref, Google Scholar
• Salemi H, Buchanan A (2020) Parsimonious formulations for low-diameter clusters. Math. Programming Comput. 12(3):493–528.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
• Validi H, Buchanan A (2020) The optimal design of low-latency virtual backbones. INFORMS J. Comput. 32(4):952–967.Abstract, Google Scholar
• Validi H, Buchanan A, Lykhovyd E (2022) Imposing contiguity constraints in political districting models. Oper. Res. 70(2):867–892.Link, 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
• Wotzlaw A (2014) On solving the maximum k-club problem. arXiv:1403.5111. Preprint, submitted March 20, https://arxiv.org/abs/1403.5111.Google Scholar
• Yezerska O, Pajouh FM, Veremyev A, Butenko S (2019) Exact algorithms for the minimum s-club partitioning problem. Ann. Oper. Res. 276(1–2):267–291.Crossref, Google Scholar
• Yu H, Paccanaro A, Trifonov V, Gerstein M (2006) Predicting interactions in protein networks by completing defective cliques. Bioinformatics 22(7):823–829.Crossref, Google Scholar
• Zachary WW (1977) An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33(4):452–473.Crossref, Google Scholar
• Zhang J, Silveira L, Validi H, Smith L, Buchanan A, Hicks IV (2026) Partitioning a graph into low-diameter clusters. https://doi.org/10.1287/ijoc.2025.1448.cd, https://github.com/INFORMSJoC/2025.1448.Google Scholar
• Zuckerman D (2006) Linear degree extractors and the inapproximability of max clique and chromatic number. Proc. Thirty-Eighth Annual ACM Sympos. Theory Comput., 681–690.Google Scholar