A branch-and-cut algorithm for graph coloring

DOI10.1016/j.dam.2005.05.022zbMath1120.90034OpenAlexW2052435807MaRDI QIDQ2489906

Publication date: 28 April 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.022

zbMATH Keywords

integer programming graph coloring branch-and-cut algorithms

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Coloring of graphs and hypergraphs (05C15)

Related Items

Cutting-plane-based algorithms for two branch vertices related spanning tree problems, A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems, Lower Bounds for the Minimal Sum Coloring Problem, A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations, A polyhedral investigation of star colorings, Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks, An exact algorithm with learning for the graph coloring problem, A DSATUR-based algorithm for the equitable coloring problem, Discrete optimization methods to fit piecewise affine models to data points, A Wide Branching Strategy for the Graph Coloring Problem, A supernodal formulation of vertex colouring with applications in course timetabling, The minimum chromatic violation problem: a polyhedral study, The minimum chromatic violation problem: a polyhedral approach, Total coloring and total matching: polyhedra and facets, An asymmetric multi-item auction with quantity discounts applied to Internet service procurement in Buenos Aires public schools, An integer programming approach to b-coloring, Fractional programming formulation for the vertex coloring problem, A branch-and-cut algorithm for the connected max-\(k\)-cut problem, Heuristic and exact algorithms for a min-max selective vehicle routing problem, A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem, Orbital branching, The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study, Maximum-weight stable sets and safe lower bounds for graph coloring, An exact approach for the vertex coloring problem, The maximum-impact coloring polytope, Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, Packing and partitioning orbitopes, Safe Lower Bounds for Graph Coloring, Coloring graphs by iterated local search traversing feasible and infeasible solutions, Ising formulations of some graph-theoretic problems in psychological research: models and methods, Solving vertex coloring problems as maximum weight stable set problems, A column generation based algorithm for the robust graph coloring problem, Polyhedral studies of vertex coloring problems: the standard formulation, Variable space search for graph coloring, Embedding a novel objective function in a two-phased local search for robust vertex coloring, A branch-and-cut procedure for the Udine course timetabling problem, A polyhedral study of the acyclic coloring problem, A new \textsf{DSATUR}-based algorithm for exact vertex coloring, Solving a multicoloring problem with overlaps using integer programming, An exact method for graph coloring, Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments, A polyhedral study of the acyclic coloring problem, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach, A one-to-one correspondence between colorings and stable sets, Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams, Dual Inequalities for Stabilized Column Generation Revisited, A note on computational approaches for the antibandwidth problem, Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation, Three algorithms for graph locally harmonious colouring, CsegGraph: a graph colouring instance generator, Graph coloring with decision diagrams

Uses Software

Cites Work