Upper bounds and heuristics for the 2-club problem

DOI10.1016/j.ejor.2010.11.023zbMath1213.90250MaRDI QIDQ541693

Filipa D. Carvalho, Maria Teresa Almeida

Publication date: 7 June 2011

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2010.11.023

zbMATH Keywords

heuristics; integer programming; combinatorial optimization; \(k\)-club problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C10: Integer programming

90C59: Approximation methods and heuristics in mathematical programming

Related Items

Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs, Integer models and upper bounds for the 3‐club problem, 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, Finding large \(k\)-clubs in undirected graphs, Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts, On biconnected and fragile subgraphs of low diameter, Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments, On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs, An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem, On structural parameterizations for the 2-club problem, The triangle \(k\)-club problem, Approximating maximum diameter-bounded subgraph in unit disk graphs, Distance-Based Clique Relaxations in Networks: s-Clique and s-Club, On the 2-Club Polytope of Graphs

Cites Work

• Unnamed Item
• Selected combinatorial problems of computational biology
• Solving the maximum edge weight clique problem via unconstrained quadratic programming
• An extended formulation approach to the edge-weighted maximal clique problem
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• Heuristics for finding \(k\)-clubs in an undirected graph
• Clique-detection models in computational biochemistry and genomics
• Mining market data: a network approach
• Novel approaches for analyzing biological networks
• Extended and discretized formulations for the maximum clique problem
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• A graph‐theoretic definition of a sociometric clique†