New integer linear programming models for the vertex coloring problem
From MaRDI portal
Publication:2294722
DOI10.1007/978-3-319-77404-6_47zbMATH Open1504.68167arXiv1706.10191OpenAlexW2964124125MaRDI QIDQ2294722FDOQ2294722
Authors: Adalat Jabrayilov, Petra Mutzel 
Publication date: 12 February 2020
Abstract: The vertex coloring problem asks for the minimum number of colors that can be assigned to the vertices of a given graph such that for all vertices v the color of v is different from the color of any of its neighbors. The problem is NP-hard. Here, we introduce new integer linear programming formulations based on partial orderings. They have the advantage that they are as simple to work with as the classical assignment formulation, since they can be fed directly into a standard integer linear programming solver. We evaluate our new models using Gurobi and show that our new simple approach is a good alternative to the best state-of-the-art approaches for the vertex coloring problem. In our computational experiments, we compare our formulations with the classical assignment formulation and the representatives formulation on a large set of benchmark graphs as well as randomly generated graphs of varying size and density. The evaluation shows that one of the new models dominates both formulations for sparse graphs, while the representatives formulation is the best for dense graphs.
Full work available at URL: https://arxiv.org/abs/1706.10191
Recommendations
- Fractional programming formulation for the vertex coloring problem
- On the asymmetric representatives formulation for the vertex coloring problem
- An exact approach for the vertex coloring problem
- Linear programming formulation of the vertex colouring problem
- Exact solution of graph coloring problems via constraint programming and column generation
Graph theory (including graph drawing) in computer science (68R10) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15)
Cited In (17)
- Graph coloring lower bounds from decision diagrams
- Expected polynomial-time randomized algorithm for graph coloring problem
- Fractional programming formulation for the vertex coloring problem
- Graph coloring with decision diagrams
- Linear programming formulation of the vertex colouring problem
- The parallel quantum algorithm for the class of optimization
- A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic
- Improving lower bounds for equitable chromatic number
- Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments
- Upper and lower bounds based on linear programming for the b-coloring problem
- Total coloring and total matching: polyhedra and facets
- New Steiner 2-designs from old ones by paramodifications
- Collective dynamics of phase-repulsive oscillators solves graph coloring problem
- Integer linear programming formulations of the filter partitioning minimization problem
- A comparison of integer programming models for the partial directed weighted improper coloring problem
- On recognizing staircase compatibility
- An incremental search heuristic for coloring vertices of a graph
Uses Software
This page was built for publication: New integer linear programming models for the vertex coloring problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294722)
