A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem

DOI10.1016/J.DISOPT.2011.05.003MaRDI QIDQ408371zbMATH OpenOpenAlexFDO

Authors Diego Delle Donne, Javier Marenco

Publication date 5 April 2012

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2011.05.003

zbMATH Keywords

adjacent colorsfrequency assignmentinteger programming

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Communication networks in operations research (90B18) Integer programming (90C10)

Recommendations

• Spectrum graph coloring and applications to Wi-Fi channel assignment
• Weighted Improper Colouring
• scientific article; zbMATH DE number 1263991
• scientific article; zbMATH DE number 1008460
• Frequency planning and ramifications of coloring

Cites work

• A branch-and-cut algorithm for graph coloring
• A column generation and branch-and-cut algorithm for the channel assignment problem
• A Column Generation Approach for Graph Coloring
• A cutting plane algorithm for graph coloring
• Cliques, holes and the vertex coloring polytope
• Erratum to ``Comparison of column generation models for channel assignment in cellular networks
• scientific article; zbMATH DE number 5540195 (Why is no real title available?)
• scientific article; zbMATH DE number 2080192 (Why is no real title available?)
• scientific article; zbMATH DE number 2086928 (Why is no real title available?)
• Models and solution techniques for frequency assignment problems
• The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization

Cited in

(5)

• Polyhedral studies of vertex coloring problems: the standard formulation
• A branch-and-bound algorithm for the minimum cut linear arrangement problem
• A Wide Branching Strategy for the Graph Coloring Problem
• A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants
• A simple branching scheme for vertex coloring problems

Describes a project that uses

Uses Software

• ABACUS
• CPLEX
• CALMA

This page was built for publication: A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem

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