An exact algorithm for the maximum \(k\)-club problem in an undirected graph
From MaRDI portal
Publication:1600883
DOI10.1016/S0377-2217(01)00133-3zbMath1008.90048MaRDI QIDQ1600883
Jean-Marie Bourjolly, Gilbert Laporte, Gilles Pesant
Publication date: 16 June 2002
Published in: European Journal of Operational Research (Search for Journal in Brave)
Applications of graph theory (05C90) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
The triangle \(k\)-club problem ⋮ A review on algorithms for maximum clique problems ⋮ Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts ⋮ Optimal approximation algorithms for maximum distance-bounded subgraph problems ⋮ Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights ⋮ Finding disjoint dense clubs in a social network ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ Two-phase heuristics for the \(k\)-club problem ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ Integer models and upper bounds for the 3‐club problem ⋮ A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques ⋮ Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ Algorithms for the maximum \(k\)-club problem in graphs ⋮ On the tractability of finding disjoint clubs in a network ⋮ On the 2-Club Polytope of Graphs ⋮ On biconnected and fragile subgraphs of low diameter ⋮ Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems ⋮ On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs ⋮ Covering a Graph with Clubs ⋮ Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ Finding lasting dense subgraphs ⋮ Parsimonious formulations for low-diameter clusters ⋮ Detecting critical node structures on graphs: A mathematical programming approach ⋮ Finding Disjoint Dense Clubs in an Undirected Graph ⋮ Analytical characterizations of some classes of optimal strongly attack-tolerant networks and their Laplacian spectra ⋮ 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 ⋮ Graph signatures: identification and optimization ⋮ Detecting large risk-averse 2-clubs in graphs with random edge failures ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ Parameterized computational complexity of finding small-diameter subgraphs ⋮ An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem ⋮ Upper bounds and heuristics for the 2-club problem ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ The maximum \(l\)-triangle \(k\)-club problem: complexity, properties, and algorithms ⋮ Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity ⋮ Computing maximum \(k\)-defective cliques in massive graphs ⋮ On the tractability of covering a graph with 2-clubs ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ On the maximum small-world subgraph problem ⋮ Exact algorithms for the minimum \(s\)-club partitioning problem ⋮ Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs ⋮ On structural parameterizations for the 2-club problem ⋮ On connected dominating sets of restricted diameter
Uses Software
Cites Work
