On the recursive largest first algorithm for graph colouring

DOI10.1080/00207160701419114zbMath1139.05024OpenAlexW2049082582MaRDI QIDQ5451459

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

zbMATH Keywords

approximation algorithmchromatic numbermaximum independent setcoloring RLF algorithmgreedy independent set algorithm

Mathematics Subject Classification ID

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

Related Items (6)

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

Cites Work

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

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