Local optimization of colorings of graphs

DOI10.1007/BF01068683MaRDI QIDQ3780451zbMATH OpenFDO

Authors Anatoly V. Anisimov

Publication date 1986

Published in Cybernetics (Search for Journal in Brave)

zbMATH Keywords

heuristic nondeterministic graph coloring algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Publication:4206748
• CHECKCOL: improved local search for graph coloring
• On graph coloring in a class of parallel local algorithms
• Publication:5752591
• scientific article; zbMATH DE number 4134072

Cites work

• scientific article; zbMATH DE number 3894828 (Why is no real title available?)
• scientific article; zbMATH DE number 3184555 (Why is no real title available?)
• A technique for colouring a graph applicable to large scale timetabling problems
• An axiomatic proof technique for parallel programs
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Depth-First Search and Linear Graph Algorithms
• New methods to color the vertices of a graph
• The Complexity of Near-Optimal Graph Coloring
• The preparation of examination time-tables using a small-store computer

Cited in

(17)

• Coloring graphs by iterated local search traversing feasible and infeasible solutions
• Generalised graph colouring by a hybrid of local search and constraint programming
• On graph coloring in a class of parallel local algorithms
• scientific article; zbMATH DE number 1452707 (Why is no real title available?)
• A range-compaction heuristic for graph coloring
• scientific article; zbMATH DE number 2115843 (Why is no real title available?)
• Graph Coloring Using Eigenvalue Decomposition
• scientific article; zbMATH DE number 4187836 (Why is no real title available?)
• Methods of local optimization for the problem of permutating bipartite graphs
• Simple decentralized graph coloring
• A Large Neighborhood Search Heuristic for Graph Coloring
• Local Algorithms for Edge Colorings in UDGs
• A new vertex coloring heuristic and corresponding chromatic number
• scientific article; zbMATH DE number 4127230 (Why is no real title available?)
• CHECKCOL: improved local search for graph coloring
• Local optima topology for the \(k\)-coloring problem
• Three algorithms for graph locally harmonious colouring

This page was built for publication: Local optimization of colorings of graphs

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