On the recursive largest first algorithm for graph colouring

DOI10.1080/00207160701419114MaRDI QIDQ5451459zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)