A new \textsf{DSATUR}-based algorithm for exact vertex coloring

DOI10.1016/j.cor.2011.10.008zbMath1250.05113OpenAlexW1991496278MaRDI QIDQ1762162

Pablo San Segundo

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.10.008

zbMATH Keywords

graphexactcolorDSATUR

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations ⋮ A branch and price algorithm for list coloring problem ⋮ Lower bounding techniques for DSATUR-based branch and bound ⋮ An exact algorithm with learning for the graph coloring problem ⋮ A DSATUR-based algorithm for the equitable coloring problem ⋮ Spectrum graph coloring and applications to Wi-Fi channel assignment ⋮ Constraint and Satisfiability Reasoning for Graph Coloring ⋮ ILP models and column generation for the minimum sum coloring problem ⋮ Solving vertex coloring problems as maximum weight stable set problems ⋮ Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks ⋮ Graph coloring with decision diagrams

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact approach for the vertex coloring problem
• Using tabu search techniques for graph coloring
• An exact bit-parallel algorithm for the maximum clique problem
• Graph colouring approaches for a satellite range scheduling problem
• A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding
• Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
• Hybrid evolutionary algorithms for graph coloring
• A graph coloring heuristic using partial solutions and a reactive tabu scheme
• A cutting plane algorithm for graph coloring
• A branch-and-cut algorithm for graph coloring
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
• A Metaheuristic Approach for the Vertex Coloring Problem
• A survey on vertex coloring problems
• Safe Lower Bounds for Graph Coloring
• A graph coloring algorithm for large scheduling problems
• 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
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Chromatic Scheduling and the Chromatic Number Problem

This page was built for publication: A new \textsf{DSATUR}-based algorithm for exact vertex coloring