A sequential elimination algorithm for computing bounds on the clique number of a graph

DOI10.1016/j.disopt.2008.01.001zbMath1160.05044OpenAlexW2115713772MaRDI QIDQ937406

Alain Hertz, Bernard Gendron, Patrick St-Louis

Publication date: 15 August 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2008.01.001

zbMATH Keywords

upper boundslower boundsclique numbermaximum cliquesequential elimination algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Extended and discretized formulations for the maximum clique problem ⋮ Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph ⋮ Cliques with maximum/minimum edge neighborhood and neighborhood density ⋮ Solving the maximum edge-weight clique problem in sparse graphs with compact formulations ⋮ Maximum cut-clique problem: ILS heuristics and a data analysis application ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• The maximum clique problem
• The sandwich theorem
• Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set
• A survey of local search methods for graph coloring
• New methods to color the vertices of a graph
• On the Shannon capacity of a graph
• An inequality for the chromatic number of a graph

This page was built for publication: A sequential elimination algorithm for computing bounds on the clique number of a graph