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 numbercoloring RLF algorithmgreedy independent set algorithmmaximum independent set

Mathematics Subject Classification ID

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

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

(9)

• Online algorithms for the maximum \(k\)-colorable subgraph problem
• A note on selective line-graphs and partition colorings
• Chromatic Gallai identities operating on Lovász number
• A graph coloring approach to the deployment scheduling and unit assignment problem
• A new efficient RLF-like algorithm for the vertex coloring problem
• Facet-inducing web and antiweb inequalities for the graph coloring polytope
• A near-real-time reduction-based algorithm for coloring massive graphs
• Extremal dependence networks for mitigating systemic risk via maximum independent sets
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT 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)