On the recursive largest first algorithm for graph colouring

DOI10.1080/00207160701419114zbMATH Open1139.05024OpenAlexW2049082582MaRDI QIDQ5451459FDOQ5451459

Authors: Gintaras Palubeckis 

Publication date: 27 March 2008

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

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

Recommendations

• A new efficient RLF-like algorithm for the vertex coloring problem
• Euro-Par 2004 Parallel Processing
• Numerical experiences with graph coloring algorithms
• Some sequential graph colouring algorithms
• scientific article; zbMATH DE number 3906523

zbMATH Keywords

approximation algorithmchromatic numbermaximum independent setcoloring RLF algorithmgreedy independent set algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• New methods to color the vertices of a graph
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
• A Column Generation Approach for Graph Coloring
• Using tabu search techniques for graph coloring
• Zero knowledge and the chromatic number
• A GRASP for coloring sparse graphs
• Cliques, holes and the vertex coloring polytope
• The combinatorics of pivoting for the maximum weight clique.

Cited In (7)

• Chromatic Gallai identities operating on Lovász number
• A graph coloring approach to the deployment scheduling and unit assignment problem
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• Facet-inducing web and antiweb inequalities for the graph coloring polytope
• Online algorithms for the maximum \(k\)-colorable subgraph problem
• A note on selective line-graphs and partition colorings
• A new efficient RLF-like algorithm for the vertex coloring problem

This page was built for publication: On the recursive largest first algorithm for graph colouring

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