An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem

DOI10.1016/j.ejor.2013.08.004zbMath1305.90303OpenAlexW1965683593MaRDI QIDQ2255969

Filipa D. Carvalho, Maria Teresa Almeida

Publication date: 18 February 2015

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

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

zbMATH Keywords

integer programmingcombinatorial optimizationclique relaxationsformulations\(k\)-clubs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of graph theory (05C90) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items

The triangle \(k\)-club problem, Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts, On Fault-Tolerant Low-Diameter Clusters in Graphs, Two-phase heuristics for the \(k\)-club problem, On the 2-Club Polytope of Graphs, Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments, Parsimonious formulations for low-diameter clusters, An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem, On the maximum small-world subgraph problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
• Upper bounds and heuristics for the 2-club problem
• Selected combinatorial problems of computational biology
• Projection, lifting and extended formulation integer and combinatorial optimization
• Solving the maximum edge weight clique problem via unconstrained quadratic programming
• A comparative analysis of several asymmetric traveling salesman problem formulations
• A classification of formulations for the (time-dependent) traveling salesman problem
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• An exact algorithm for the maximum \(k\)-club problem 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
• Graphs as models of communication network vulnerability: Connectivity and persistence
• A graph‐theoretic definition of a sociometric clique†
• Integer models and upper bounds for the 3‐club problem