Heuristics for finding \(k\)-clubs in an undirected graph

DOI10.1016/S0305-0548(99)00047-7zbMath0955.91051OpenAlexW2136955214MaRDI QIDQ1977620

Gilbert Laporte, Gilles Pesant, Jean-Marie Bourjolly

Publication date: 4 March 2001

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0305-0548(99)00047-7

zbMATH Keywords

heuristicsundirected graph\(k\)-clubs\(k\)-cliques

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Approximation methods and heuristics in mathematical programming (90C59) Graph theory (05C99)

Related Items (28)

The triangle \(k\)-club problem ⋮ Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts ⋮ Finding disjoint dense clubs in a social network ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ Two-phase heuristics for the \(k\)-club problem ⋮ Frequency-driven tabu search for the maximum \(s\)-plex problem ⋮ Integer models and upper bounds for the 3‐club problem ⋮ Algorithms for the maximum \(k\)-club problem in graphs ⋮ An opposition-based memetic algorithm for the maximum quasi-clique problem ⋮ On atomic cliques in temporal graphs ⋮ On the 2-Club Polytope of Graphs ⋮ On biconnected and fragile subgraphs of low diameter ⋮ On solving simplified diversified top-\(k\,s\)-plex problem ⋮ Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems ⋮ On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs ⋮ Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ Parsimonious formulations for low-diameter clusters ⋮ Finding Disjoint Dense Clubs in an Undirected Graph ⋮ Finding large \(k\)-clubs in undirected graphs ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs ⋮ Parameterized computational complexity of finding small-diameter subgraphs ⋮ Upper bounds and heuristics for the 2-club problem ⋮ The maximum \(l\)-triangle \(k\)-club problem: complexity, properties, and algorithms ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ Exact algorithms for the minimum \(s\)-club partitioning problem ⋮ On structural parameterizations for the 2-club problem ⋮ An exact algorithm for the maximum \(k\)-club problem in an undirected graph

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Solving the maximum clique problem using a tabu search approach
• Some genuine graph models in anthropology
• Three‐dimensional blockmodels
• A formal theory of social power
• A graph‐theoretic definition of a sociometric clique†
• On the connectivity of social networks†
• Reducibility among Combinatorial Problems
• Algorithm 457: finding all cliques of an undirected graph

This page was built for publication: Heuristics for finding \(k\)-clubs in an undirected graph