An exact algorithm for the maximum k-club problem in an undirected graph
From MaRDI portal
Publication:1600883
DOI10.1016/S0377-2217(01)00133-3zbMATH Open1008.90048MaRDI QIDQ1600883FDOQ1600883
Authors: Jean-Marie Bourjolly, G. Laporte, Gilles Pesant 
Publication date: 16 June 2002
Published in: European Journal of Operational Research (Search for Journal in Brave)
Recommendations
Applications of graph theory (05C90) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Integer programming (90C10)
Cites Work
- Algorithm 457: finding all cliques of an undirected graph
- Title not available (Why is that?)
- Solving the maximum clique problem using a tabu search approach
- Heuristics for finding \(k\)-clubs in an undirected graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- A graph‐theoretic definition of a sociometric clique†
- Three‐dimensional blockmodels
Cited In (52)
- Efficient branch-and-bound algorithms for finding triangle-constrained 2-clubs
- The parameterized complexity of \(s\)-club with triangle and seed constraints
- Finding conserved low-diameter subgraphs in social and biological networks
- On the parameterized complexity of non-hereditary relaxations of clique
- An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem
- Detecting critical node structures on graphs: a mathematical programming approach
- Optimization problems for the maximum \(k\)-plex
- Parsimonious formulations for low-diameter clusters
- On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs
- On the maximum small-world subgraph problem
- The triangle \(k\)-club problem
- On the tractability of finding disjoint clubs in a network
- On biconnected and fragile subgraphs of low diameter
- Parameterized computational complexity of finding small-diameter subgraphs
- A branch-and-price-and-cut method for computing an optimal bramble
- Graph signatures: identification and optimization
- Exact algorithms for the minimum \(s\)-club partitioning problem
- Covering a graph with clubs
- Correction to: ``Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts
- Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts
- Optimal approximation algorithms for maximum distance-bounded subgraph problems
- Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity
- Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
- Distance-based clique relaxations in networks: \(s\)-clique and \(s\)-club
- On the 2-club polytope of graphs
- Finding lasting dense subgraphs
- Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights
- Computing maximum \(k\)-defective cliques in massive graphs
- The maximum \(l\)-triangle \(k\)-club problem: complexity, properties, and algorithms
- On connected dominating sets of restricted diameter
- Finding disjoint dense clubs in a social network
- Finding Disjoint Dense Clubs in an Undirected Graph
- Two-phase heuristics for the \(k\)-club problem
- Algorithms for the maximum \(k\)-club problem in graphs
- On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
- The parameterized complexity of \(s\)-club with triangle and seed constraints
- Approximating maximum diameter-bounded subgraph in unit disk graphs
- Approximating maximum diameter-bounded subgraph in unit disk graphs
- Upper bounds and heuristics for the 2-club problem
- Analytical characterizations of some classes of optimal strongly attack-tolerant networks and their Laplacian spectra
- Finding large \(k\)-clubs in undirected graphs
- On Fault-Tolerant Low-Diameter Clusters in Graphs
- A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques
- On the tractability of covering a graph with 2-clubs
- Integer models and upper bounds for the 3-club problem
- A review on algorithms for maximum clique problems
- Title not available (Why is that?)
- On provably best construction heuristics for hard combinatorial optimization problems
- Detecting large risk-averse 2-clubs in graphs with random edge failures
- Heuristics for finding \(k\)-clubs in an undirected graph
- Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments
- Multivariate algorithmics for finding cohesive subnetworks
Uses Software
This page was built for publication: An exact algorithm for the maximum \(k\)-club problem in an undirected graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1600883)
