Graph coloring with decision diagrams

DOI10.1007/S10107-021-01662-XzbMATH Open1489.90165OpenAlexW3164824051MaRDI QIDQ2118148FDOQ2118148

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

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

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)

Cites Work

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

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

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)