On Fault-Tolerant Low-Diameter Clusters in Graphs

References

• Alba RD (1973) A graph-theoretic definition of a sociometric clique. J. Math. Sociol. 3(1):113–126.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
• Alon U (2007) Network motifs: theory and experimental approaches. Nature Rev. Genetics 8:450–461.Crossref, Google Scholar
• Asahiro Y, Miyano E, Samizo K (2010) Approximating maximum diameter-bounded subgraphs. López-Ortiz A, ed. LATIN 2010: Theoretical Informatics (Springer, Berlin), 615–626.Crossref, Google Scholar
• Asahiro Y, Doi Y, Miyano E, Samizo K, Shimizu H (2018) Optimal approximation algorithms for maximum distance-bounded subgraph problems. Algorithmica 80(6):1834–1856.Crossref, Google Scholar
• Bader DA, Meyerhenke H, Sanders P, Wagner D, eds. (2013) Graph Partitioning and Graph Clustering: Tenth Dimacs Implementation Challenge Workshop, February 13–14, Georgia Institute of Technology, Atlanta, GA. Contemporary Mathematics 588 (American Mathematical Society and Center for Discrete Mathematics and Theoretical Computer Science, Providence, RI).Crossref, Google Scholar
• Baier G, Erlebach T, Hall A, Köhler E, Kolman P, Pangrác O, Schilling H, et al. (2010) Length-bounded cuts and flows. ACM Trans. Algorithms 7(1):4.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
• Batagelj V, Zaveršnik M (2011) Fast algorithms for determining (generalized) core groups in social networks. Adv. Data Anal. Classification 5:129–145.Google Scholar
• Botton Q, Fortz B, Gouveia L (2015) On the hop-constrained survivable network design problem with reliable edges. Comput. Oper. Res. 64:159–167.Crossref, Google Scholar
• Botton Q, Fortz B, Gouveia L, Poss M (2013) Benders decomposition for the hop-constrained survivable network design problem. INFORMS J. Comput. 25(1):13–26.Link, Google Scholar
• Bourjolly JM, Laporte G, Pesant G (2000) Heuristics for finding k-clubs in an undirected graph. Comput. Oper. Res. 27:559–569.Crossref, 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:21–28.Crossref, Google Scholar
• Caccetta L (1979) On extremal graphs with given diameter and connectivity. Ann. New York Acad. Sci. 328(1):76–94.Crossref, Google Scholar
• Carmesin J, Diestel R, Hamann M, Hundertmark F (2014) k-blocks: A connectivity invariant for graphs. SIAM J. Discrete Math. 28(4):1876–1891.Crossref, Google Scholar
• Carr RD, Lancia G (2002) Compact vs. exponential-size LP relaxations. Oper. Res. Lett. 30(1):57–65.Crossref, Google Scholar
• Carvajal R, Constantino M, Goycoolea M, Vielma JP, Weintraub A (2013) Imposing connectivity constraints in forest planning models. Oper. Res. 61(4):824–836.Link, Google Scholar
• Chang MS, Hung LJ, Lin CR, Su PC (2013) Finding large k-clubs in undirected graphs. Computing 95(9):739–758.Crossref, Google Scholar
• Chen YP, Liestman AL, Liu J (2005) Clustering algorithms for ad hoc wireless networks. Pan Y, Xiao Y, eds. Ad Hoc and Sensor Networks, Wireless Networks and Mobile Computing (Nova Science Publishers, New York), 145–164.Google Scholar
• Cook DJ, Holder LB (2006) Mining Graph Data (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Dagum L, Enon R (1998) OpenMP: An industry standard API for shared-memory programming. IEEE Comput. Sci. Engrg. 5(1):46–55.Crossref, Google Scholar
• Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Faudree RJ, Gould RJ, Powell JS (2012) Property Pd,m and efficient design of reliable networks. Networks 60(3):167–178.Crossref, Google Scholar
• Ford L Jr, Fulkerson DR (1956) Maximal flow through a network. Canadian J. Math. 8:399–404.Crossref, Google Scholar
• Gendreau M, Soriano P, Salvail L (1993) Solving the maximum clique problem using a tabu search approach. Ann. Oper. Res. 41(4):385–403.Crossref, Google Scholar
• Golovach PA, Heggernes P, Kratsch D, Rafiey A (2014) Finding clubs in graph classes. Discrete Appl. Math. 174:57–65.Crossref, Google Scholar
• Gould N, Scott J (2016) A note on performance profiles for benchmarking software. ACM Trans. Math. Software 43(2):1–5.Crossref, Google Scholar
• Gouveia L, Leitner M (2017) Design of survivable networks with vulnerability constraints. Eur. J. Oper. Res. 258(1):89–103.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimization, 2nd ed. (Springer-Verlag, Berlin).Crossref, Google Scholar
• Grötschel M, Monma CL, Stoer M (1992) Facets for polyhedra arising in the design of communication networks with low-connectivity constraints. SIAM J. Optim. 2(3):474–504.Crossref, Google Scholar
• Gupta G, Younis M (2003) Fault-tolerant clustering of wireless sensor networks. Proc. IEEE Wireless Communications and Networking (IEEE, New York), 1579–1584.Google Scholar
• Gurobi Optimization L (2020) Gurobi optimizer reference manual. Accessed August 29, 2022, http://www.gurobi.com.Google Scholar
• Hartung S, Komusiewicz C, Nichterlein A, Suchý O (2015) On structural parameterizations for the 2-club problem. Discrete Appl. Math. 185:79–92.Crossref, Google Scholar
• Hopcroft J, Tarjan R (1973) Algorithm 447: Efficient algorithms for graph manipulation. Comm. ACM 16(6):372–378.Crossref, Google Scholar
• Itai A, Perl Y, Shiloach Y (1982) The complexity of finding maximum disjoint paths with length constraints. Networks 12(3):277–286.Crossref, Google Scholar
• Komusiewicz C, Nichterlein A, Niedermeier R, Picker M (2019) Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: Theory and experiments. Eur. J. Oper. Res. 275(3):846–864.Crossref, Google Scholar
• Langguth J, Manne F, Sanders P (2010) Heuristic initialization for bipartite matching problems. J. Experiment. Algorithmics 15:1–1.Crossref, Google Scholar
• Lawler E (1976) Combinatorial Optimization: Networks and Matroids (Holt, Rinehart, and Winston, New York).Google Scholar
• Lewis JM, Yannakakis M (1980) The node-deletion problem for hereditary properties is NP-complete. J. Comput. System Sci. 20(2):219–230.Crossref, Google Scholar
• Lovász L, Neumann-Lara V, Plummer M (1978) Mengerian theorems for paths of bounded length. Period Math. Hungary 9(4):269–276.Crossref, Google Scholar
• Lu Y, Moradi E, Balasundaram B (2018) Correction to: Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts. Optim. Lett. 12(8):1959–1969.Crossref, Google Scholar
• Luce RD (1950) Connectivity and generalized cliques in sociometric group structure. Psychometrika 15(2):169–190.Crossref, Google Scholar
• Magun J (1998) Greedy matching algorithms, an experimental study. ACM J. Experiment. Algorithmics 3:6.Crossref, Google Scholar
• Martin RK (1991) Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3):119–128.Crossref, Google Scholar
• Matula DW (1978) k-blocks and ultrablocks in graphs. J. Combinatorial Theory Ser. B 24(1):1–13.Crossref, Google Scholar
• Matula DW, Beck LL (1983) Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3):417–427.Crossref, Google Scholar
• Menger K (1927) Zur allgemeinen kurventheorie. Fundamentals Math. 10:95–115.Google Scholar
• Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002) Network motifs: Simple building blocks of complex networks. Science 298:824–827.Crossref, Google Scholar
• Möhring R, Müller-Hannemann M (1995) Cardinality matching: Heuristic search for augmenting paths. Technical report 439, Technische Universität, Berlin.Google Scholar
• Mokken RJ (1979) Cliques, clubs and clans. Qualitative Quantitative 13(2):161–173.Crossref, Google Scholar
• Moradi E, Balasundaram B (2018) Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts. Optim. Lett. 12(8):1947–1957.Crossref, Google Scholar
• Pajouh FM, Balasundaram B (2012) On inclusionwise maximal and maximum cardinality k-clubs in graphs. Discrete Optim. 9(2):84–97.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
• Rose D, Tarjan R, Lueker G (1976) Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2):266–283.Crossref, Google Scholar
• Salemi H, Buchanan A (2020) Parsimonious formulations for low-diameter clusters. Math. Programming Comput. 12(3):493–528.Crossref, Google Scholar
• Schäfer A (2009) Exact algorithms for s-club finding and related problems. MS thesis, Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität, Jena, Germany.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
• 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, Boginski V, Pasiliao EL, Prokopyev OA (2022) On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs. Eur. J. Oper. Res. 297(1):86–101.Crossref, Google Scholar
• Vijayan K, Murty USR (1964) On accessibility in graphs. Sankhya Ser. A 26(2–3):299–302.Google Scholar
• Walteros JL, Buchanan A (2020) Why is maximum clique often easy in practice? Oper. Res. 68(6):1866–1895.Link, Google Scholar
• Wang Y, Buchanan A, Butenko S (2017) On imposing connectivity constraints in integer programs. Math. Programming 166(1):241–271.Crossref, Google Scholar
• Watts D, Strogatz S (1998) Collective dynamics of “small-world” networks. Nature 393:440–442.Crossref, Google Scholar
• West D (2001) Introduction to Graph Theory (Prentice-Hall, Upper Saddle River, NJ).Google Scholar
• Yezerska O, Pajouh FM, Butenko S (2017) On biconnected and fragile subgraphs of low diameter. Eur. J. Oper. Res. 263(2):390–400.Crossref, Google Scholar
• Zhang LV, King OD, Wong SL, Goldberg DS, Tong AH, Lesage G, Andrews B, et al. (2005) Motifs, themes and thematic maps of an integrated saccharomyces cerevisiae interaction network. J. Biology 4(2):6.Crossref, Google Scholar
• Zheng J, Wang P, Li C, Mouftah HT (2008) An efficient fault-prevention clustering protocol for robust underwater sensor networks. Proc. IEEE Internat. Conf. on Comm., 2802–2807.Google Scholar