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
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