A branch-and-cut algorithm for graph coloring
From MaRDI portal
Publication:2489906
DOI10.1016/J.DAM.2005.05.022zbMATH Open1120.90034OpenAlexW2052435807MaRDI QIDQ2489906FDOQ2489906
Authors: Paula Zabala, Isabel Méndez-Díaz 
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
Recommendations
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the facial structure of set packing polyhedra
- Frozen development in graph coloring
- On the solution of traveling salesman problems
- Title not available (Why is that?)
- Facets of the graph coloring polytope
- A graph coloring algorithm for large scheduling problems
- Title not available (Why is that?)
- New methods to color the vertices of a graph
- The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
- On the facial structure of the set covering polytope
- A Column Generation Approach for Graph Coloring
- Using tabu search techniques for graph coloring
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An exact algorithm for the maximum stable set problem
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- Title not available (Why is that?)
- A Pruning Procedure for Exact Graph Coloring
- Title not available (Why is that?)
- A polyhedral approach for graph coloring
Cited In (65)
- A one-to-one correspondence between colorings and stable sets
- Fractional programming formulation for the vertex coloring problem
- Coloring graphs by iterated local search traversing feasible and infeasible solutions
- An exact method for graph coloring
- Exact solution of graph coloring problems via constraint programming and column generation
- A Wide Branching Strategy for the Graph Coloring Problem
- A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
- Solving a multicoloring problem with overlaps using integer programming
- A simple branching scheme for vertex coloring problems
- Lower bounds for the minimal sum coloring problem
- Graph coloring with decision diagrams
- A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations
- A polyhedral investigation of star colorings
- Dual inequalities for stabilized column generation revisited
- A polyhedral approach for graph coloring
- An exact approach for the vertex coloring problem
- An integer programming approach to b-coloring
- CsegGraph: a graph colouring instance generator
- Polyhedral studies of vertex coloring problems: the standard formulation
- Ising formulations of some graph-theoretic problems in psychological research: models and methods
- An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
- Packing and partitioning orbitopes
- The minimum chromatic violation problem: a polyhedral study
- Solving vertex coloring problems as maximum weight stable set problems
- Orbital branching
- Solving graph coloring problems with the Douglas-Rachford algorithm
- Title not available (Why is that?)
- Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks
- A supernodal formulation of vertex colouring with applications in course timetabling
- A branch-and-cut procedure for the Udine course timetabling problem
- A new \textsf{DSATUR}-based algorithm for exact vertex coloring
- Branch-cut-and-propagate for the maximum \(k\)-colorable subgraph problem with symmetry
- Facets of the graph coloring polytope
- Heuristic and exact algorithms for a min-max selective vehicle routing problem
- Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments
- Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
- An exact algorithm with learning for the graph coloring problem
- A DSATUR-based algorithm for the equitable coloring problem
- Total coloring and total matching: polyhedra and facets
- A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems
- A note on computational approaches for the antibandwidth problem
- Discrete optimization methods to fit piecewise affine models to data points
- Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
- Variable space search for graph coloring
- Embedding a novel objective function in a two-phased local search for robust vertex coloring
- Maximum-weight stable sets and safe lower bounds for graph coloring
- A branch-and-cut algorithm for partition coloring
- Safe lower bounds for graph coloring
- A cutting plane algorithm for graph coloring
- An asymmetric multi-item auction with quantity discounts applied to Internet service procurement in Buenos Aires public schools
- The minimum chromatic violation problem: a polyhedral approach
- 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
- Three algorithms for graph locally harmonious colouring
- A column generation based algorithm for the robust graph coloring problem
- A Pruning Procedure for Exact Graph Coloring
- Cutting-plane-based algorithms for two branch vertices related spanning tree problems
- A polyhedral study of the acyclic coloring problem
- A polyhedral study of the acyclic coloring problem
- Conflict optimization for binary CSP applied to minimum partition into plane subgraphs and graph coloring
- Minimum partition into plane subgraphs: the CG:SHOP challenge 2022
- Solving the list coloring problem through a branch-and-price algorithm
- A branch-and-cut algorithm for the connected max-\(k\)-cut problem
- The maximum-impact coloring polytope
- The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study
Uses Software
This page was built for publication: A branch-and-cut algorithm for graph coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489906)
