A global optimization approach for solving the maximum clique problem

DOI10.1080/00207169008803851zbMath0825.68488OpenAlexW2071702553MaRDI QIDQ4009762

A. T. Phillips, Panos M. Pardalos

Publication date: 27 September 1992

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207169008803851

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items (32)

Annealed replication: A new heuristic for the maximum clique problem ⋮ Maximum cliques of hypergraphs and polynomial optimization ⋮ A spinorial formulation of the maximum clique problem of a graph ⋮ Solving the maximum clique problem using a tabu search approach ⋮ A Motzkin-Straus type result for 3-uniform hypergraphs ⋮ An Efficient Approximation Algorithm for Finding a Maximum Clique Using Hopfield Network Learning ⋮ 0-1 Quadratic programming approach for optimum solutions of two scheduling problems ⋮ A graph-theoretic method for organizing overlapping clusters into trees, multiple trees, or extended trees ⋮ An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network ⋮ Unnamed Item ⋮ Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation ⋮ An algorithm for finding a maximum weighted independent set in an arbitrary graph ⋮ On Motzkin-Straus type results for non-uniform hypergraphs ⋮ A General Regularized Continuous Formulation for the Maximum Clique Problem ⋮ On graph-Lagrangians of hypergraphs containing dense subgraphs ⋮ On Lagrangians of \(r\)-uniform hypergraphs ⋮ Genetic algorithmic approach to find the maximum weight independent set of a graph ⋮ A continuous characterization of the maximum vertex-weighted clique in hypergraphs ⋮ Dominant-set clustering: a review ⋮ A nonconvex quadratic optimization approach to the maximum edge weight clique problem ⋮ A tutorial on branch and cut algorithms for the maximum stable set problem ⋮ Some Motzkin-Straus type results for non-uniform hypergraphs ⋮ Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs ⋮ Exact bounds on the order of the maximum clique of a graph. ⋮ Lagrangean decompositions for the unconstrained binary quadratic programming problem ⋮ A generalization of the Motzkin-Straus theorem to hypergraphs ⋮ A sublevel moment-SOS hierarchy for polynomial optimization ⋮ On the maxima of Motzkin-Straus programs and cliques of graphs ⋮ Continuous cubic formulations for cluster detection problems in networks ⋮ A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem ⋮ The maximum clique problem ⋮ Modelling competitive Hopfield networks for the maximum clique problem

Cites Work

• Unnamed Item
• Constrained global optimization: algorithms and applications
• Clique detection for nondirected graphs: Two new algorithms
• Finding a Maximum Clique in an Arbitrary Graph
• Determining the number of internal stability of a graph
• Finding a Maximum Independent Set
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Upper Bounds on the Order of a Clique of a Graph
• Algorithm 457: finding all cliques of an undirected graph

This page was built for publication: A global optimization approach for solving the maximum clique problem