Graph coloring with decision diagrams

DOI10.1007/S10107-021-01662-XMaRDI QIDQ2118148zbMATH OpenOpenAlexFDO

Authors Willem-Jan van Hoeve

Publication date 22 March 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-021-01662-x

zbMATH Keywords

integer programminggraph coloringdecision diagrams

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Graph coloring lower bounds from decision diagrams
• Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
• A Column Generation Approach for Graph Coloring
• Incorporating bounds from decision diagrams into integer programming
• A Pruning Procedure for Exact Graph Coloring

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 939919 (Why is no real title available?)
• scientific article; zbMATH DE number 3353170 (Why is no real title available?)
• A Column Generation Approach for Graph Coloring
• A branch-and-cut algorithm for graph coloring
• A cutting plane algorithm for graph coloring
• A local search framework for compiling relaxed decision diagrams
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• A technique for colouring a graph applicable to large scale timetabling problems
• An exact approach for the vertex coloring problem
• An improved DSATUR-based branch-and-bound algorithm for the vertex coloring problem
• Binary Decision Diagrams
• Branching Programs and Binary Decision Diagrams
• Chromatic Scheduling and the Chromatic Number Problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Constructions and in-place operations for MDDs based constraints
• Decision diagrams for optimization
• Discrete optimization with decision diagrams
• Exact solution of graph coloring problems via constraint programming and column generation
• Graph coloring for air traffic flow management
• Graph coloring lower bounds from decision diagrams
• Graph-Based Algorithms for Boolean Function Manipulation
• Manipulating MDD relaxations for combinatorial optimization
• Maximum-weight stable sets and safe lower bounds for graph coloring
• New integer linear programming models for the vertex coloring problem
• New methods to color the vertices of a graph
• On finding the optimal BDD relaxation
• On the application of graph colouring techniques in round-robin sports scheduling
• Optimization Bounds from Binary Decision Diagrams
• Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams

Cited in

(4)

• Graph coloring lower bounds from decision diagrams
• Improved Peel-and-Bound: Methods for Generating Dual Bounds with Multivalued Decision Diagrams
• Column elimination for capacitated vehicle routing problems
• Decision Diagrams for Discrete Optimization: A Survey of Recent Advances

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Graph coloring with decision diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118148)