An extended formulation approach to the edge-weighted maximal clique problem
From MaRDI portal
Publication:1278438
DOI10.1016/0377-2217(95)00299-5zbMath0926.90086OpenAlexW2135702200WikidataQ60395646 ScholiaQ60395646MaRDI QIDQ1278438
Kyungchul Park, Sungsoo Park, Kyungsik Lee
Publication date: 22 February 1999
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0377-2217(95)00299-5
integer programmingextended formulationmaximal clique problemcutting-plane/facet-generation algorithm
Related Items (26)
Quadratic bottleneck knapsack problems ⋮ A new family of facet defining inequalities for the maximum edge-weighted clique problem ⋮ The effect of strengthened linear formulations on improving the lower bounds for the part families with precedence constraints problem ⋮ A review on algorithms for maximum clique problems ⋮ A polyhedral approach for a constrained quadratic 0-1 problem ⋮ An iterated ``hyperplane exploration approach for the quadratic knapsack problem ⋮ The quadratic knapsack problem -- a survey ⋮ An efficient local search algorithm for solving maximum edge weight clique problem in large graphs ⋮ Exact Solution Algorithms for the Chordless Cycle Problem ⋮ A general purpose exact solution method for mixed integer concave minimization problems ⋮ A new branch-and-bound algorithm for the maximum edge-weighted clique problem ⋮ On the Approximability of the Minimum Weight $t$-partite Clique Problem ⋮ New facets and a branch-and-cut algorithm for the weighted clique problem. ⋮ 2-approximation algorithm for finding a clique with minimum weight of vertices and edges ⋮ Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph ⋮ 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 ⋮ Disconnecting graphs by removing vertices: a polyhedral approach ⋮ Upper bounds and heuristics for the 2-club problem ⋮ Solving the maximum edge-weight clique problem in sparse graphs with compact formulations ⋮ A Lagrangian relaxation approach to the edge-weighted clique problem ⋮ Tightening concise linear reformulations of 0-1 cubic programs ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations ⋮ Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem ⋮ Solving the 0-1 quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm
Cites Work
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Facets for the cut cone. I
- Facets for the cut cone. II: Clique-web inequalities
- A cutting-plane approach to the edge-weighted maximal clique problem
- Min-cut clustering
- The cut polytope and the Boolean quadric polytope
- The perfectly matchable subgraph polytope of a bipartite graph
- Heuristically determining cliques of given cardinality and with minimal cost within weighted complete graphs
- Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Weighted k‐cardinality trees: Complexity and polyhedral structure
- Heuristic and Special Case Algorithms for Dispersion Problems
- Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
This page was built for publication: An extended formulation approach to the edge-weighted maximal clique problem
