Iterative coloring extension of a maximum clique

DOI10.1002/nav.1033zbMath1009.90121MaRDI QIDQ4544221

Paolo Dell'Olmo, Massimiliano Caramia

Publication date: 12 August 2002

Published in: Naval Research Logistics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/nav.1033

zbMATH Keywords

combinatorial optimization; lower bound; branch and bound algorithm; maximum clique; exact coloring

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90C27: Combinatorial optimization

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

On the queen graphs coloring problem., Dynamic \(F\)-free coloring of graphs, An immune algorithm with stochastic aging and Kullback entropy for the chromatic number problem, Coloring graphs by iterated local search traversing feasible and infeasible solutions, Embedding a novel objective function in a two-phased local search for robust vertex coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• An introduction to timetabling
• Finding maximum cliques in arbitrary and in special graphs
• Network-based heuristics for constraint-satisfaction problems
• Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths
• Some simplified NP-complete graph problems
• Consistency in networks of relations
• Graph coloring with adaptive evolutionary algorithms
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
• Genetic and hybrid algorithms for graph coloring
• A graph coloring algorithm for large scheduling problems
• A Sufficient Condition for Backtrack-Free Search
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• A Pruning Procedure for Exact Graph Coloring
• New methods to color the vertices of a graph
• Register Allocation in Structured Programs
• A Column Generation Approach for Graph Coloring
• Chromatic Scheduling and the Chromatic Number Problem