Lower bounding techniques for DSATUR-based branch and bound

DOI10.1016/j.endm.2016.03.020zbMath1351.90044OpenAlexW2399534786WikidataQ57659034 ScholiaQ57659034MaRDI QIDQ325423

Virginie Gabrel, Fabio Furini, Ian-Christopher Ternier

Publication date: 18 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2016.03.020

zbMATH Keywords

branch-and-bound algorithmgraph coloringDSATUR

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10)

Related Items (2)

Constraint and Satisfiability Reasoning for Graph Coloring ⋮ Solving vertex coloring problems as maximum weight stable set problems

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• An exact approach for the vertex coloring problem
• A fast algorithm for the maximum clique problem
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• Maximum-weight stable sets and safe lower bounds for graph coloring
• A one-to-one correspondence between colorings and stable sets
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
• A Wide Branching Strategy for the Graph Coloring Problem
• A survey on vertex coloring problems
• New methods to color the vertices of a graph
• A Column Generation Approach for Graph Coloring

This page was built for publication: Lower bounding techniques for DSATUR-based branch and bound