Solving the maximum edge-weight clique problem in sparse graphs with compact formulations

DOI10.1007/s13675-014-0028-1zbMath1307.90109OpenAlexW2079439262MaRDI QIDQ2260912

Pedro Martins, Luís Gouveia

Publication date: 12 March 2015

Published in: EURO Journal on Computational Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13675-014-0028-1

zbMATH Keywords

sparse graphsinteger formulationsclique's edge neighborhoodmaximum edge-weight clique problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Integer programming (90C10)

Related Items (9)

Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ An efficient local search algorithm for solving maximum edge weight clique problem in large graphs ⋮ Complexity and heuristics for the weighted max cut‐clique problem ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph ⋮ A nonconvex quadratic optimization approach to the maximum edge weight clique problem ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ Common Object Discovery as Local Search for Maximum Weight Cliques in a Global Object Similarity Graph ⋮ A maximum edge-weight clique extraction algorithm based on branch-and-bound

Cites Work

• Unnamed Item
• Clustering of high throughput gene expression data
• A sequential elimination algorithm for computing bounds on the clique number of a graph
• Approximating the maximum vertex/edge weighted clique using local search
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Cliques and clustering: A combinatorial approach
• An extended formulation approach to the edge-weighted maximal clique problem
• A cutting-plane approach to the edge-weighted maximal clique problem
• A multi-KP modeling for the maximum-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
• Mathematical programming in computational biology: an annotated bibliography
• Cliques with maximum/minimum edge neighborhood and neighborhood density
• Enhancing discretized formulations: the knapsack reformulation and the star reformulation
• On the capacitated concentrator location problem: a reformulation by discretization
• Extended and discretized formulations for the maximum clique problem
• TWO-DIMENSIONAL D^- DONOR IN A STRONG MAGNETIC FIELD
• New methods to color the vertices of a graph
• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
• A Lagrangian relaxation approach to the edge-weighted clique problem

This page was built for publication: Solving the maximum edge-weight clique problem in sparse graphs with compact formulations