Iterative coloring extension of a maximum clique

DOI10.1002/NAV.1033MaRDI QIDQ4544221zbMATH OpenOpenAlexFDO

Authors Massimiliano Caramia, Paolo Dell'Olmo

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 optimizationmaximum cliquelower boundbranch and bound algorithmexact coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Recommendations

• scientific article; zbMATH DE number 956855
• Relaxed approximate coloring in exact maximum clique search
• Bounding vertex coloring by truncatedmultistage branch and bound
• An improved DSATUR-based branch-and-bound algorithm for the vertex coloring problem
• A fast algorithm for the maximum clique problem

Cites work

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

Cited in

(10)

• Relaxed approximate coloring in exact maximum clique search
• 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
• Bounding vertex coloring by truncatedmultistage branch and bound
• Iterated colorings of graphs.
• Dynamic \(F\)-free coloring of graphs
• Infra-chromatic bound for exact maximum clique search
• Embedding a novel objective function in a two-phased local search for robust vertex coloring
• On the queen graphs coloring problem.
• Coloring the Maximal Cliques of Graphs

This page was built for publication: Iterative coloring extension of a maximum clique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4544221)