Coloring large graphs based on independent set extraction

DOI10.1016/j.cor.2011.04.002zbMath1250.05007OpenAlexW2016102370MaRDI QIDQ1761974

Jin-Kao Hao, Qinghua Wu

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.04.002

zbMATH Keywords

tabu searchgraph coloringindependent setpreprocessingmemetic search\textsf{EXTRACOL}

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

A review on algorithms for maximum clique problems ⋮ An exact algorithm with learning for the graph coloring problem ⋮ An adaptive multistart tabu search approach to solve the maximum clique problem ⋮ Chromatic Schultz and Gutman polynomials of Jahangir graphs \(J_{2, m}\) and \(J_{3, m}\) ⋮ Maximum-weight stable sets and safe lower bounds for graph coloring ⋮ Computing lower bounds for minimum sum coloring and optimum cost chromatic partition ⋮ An effective heuristic algorithm for sum coloring of graphs ⋮ Improving the extraction and expansion method for large graph coloring ⋮ Team selection for prediction tasks ⋮ EXTRACOL ⋮ Unnamed Item ⋮ INFORMED REACTIVE TABU SEARCH FOR GRAPH COLORING ⋮ AN EXTRACTION AND EXPANSION APPROACH FOR GRAPH COLORING

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• Some experiments with simulated annealing for coloring graphs
• Graph colouring approaches for a satellite range scheduling problem
• A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding
• Variable space search for graph coloring
• An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring
• Graph coloring by multiagent fusion search
• A search space ``cartography for guiding graph coloring heuristics
• Improving heuristics for the frequency assignment problem
• On a graph-theoretical model for cyclic register allocation
• A variable neighborhood search for graph coloring.
• A fast algorithm for the maximum clique problem
• Genetic and hybrid algorithms for graph coloring
• Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs
• Hybrid evolutionary algorithms for graph coloring
• Adaptive tabu search for course timetabling
• A graph-based hyper-heuristic for educational timetabling problems
• A graph coloring heuristic using partial solutions and a reactive tabu scheme
• An adaptive memory algorithm for the \(k\)-coloring problem
• A survey of local search methods for graph coloring
• A Metaheuristic Approach for the Vertex Coloring Problem
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• An application of graph coloring to printed circuit testing
• A GRASP for coloring sparse graphs