Solving vertex coloring problems as maximum weight stable set problems
From MaRDI portal
Publication:516805
DOI10.1016/J.DAM.2016.09.018zbMATH Open1358.05098DBLPjournals/dam/CornazFM17OpenAlexW2526286943WikidataQ57659018 ScholiaQ57659018MaRDI QIDQ516805FDOQ516805
Enrico Malaguti, Fabio Furini, Denis Cornaz
Publication date: 15 March 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2016.09.018
Recommendations
Cites Work
- Algorithms for the bin packing problem with conflicts
- A fast algorithm for the maximum clique problem
- A new \textsf{DSATUR}-based algorithm for exact vertex coloring
- A branch-and-cut algorithm for graph coloring
- A survey on vertex coloring problems
- A graph coloring algorithm for large scheduling problems
- 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
- On the asymmetric representatives formulation for the vertex coloring problem
- An introduction to timetabling
- A one-to-one correspondence between colorings and stable sets
- Exact solution of graph coloring problems via constraint programming and column generation
- Lower bounding techniques for DSATUR-based branch and bound
- A polyhedral approach for the equitable coloring problem
- A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
- Models and heuristic algorithms for a weighted vertex coloring problem
- Exact weighted vertex coloring via branch-and-price
- A note on the Cornaz-Jost transformation to solve the graph coloring problem
- Chromatic Gallai identities operating on Lovász number
- A branch-and-price algorithm for the bin packing problem with conflicts
Cited In (15)
- A one-to-one correspondence between colorings and stable sets
- A branch-and-cut algorithm for the edge interdiction clique problem
- On Monte Carlo tree search for weighted vertex coloring
- Monte Carlo tree search with adaptive simulation: a case study on weighted vertex coloring
- A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems
- An exact algorithm for the edge coloring by total labeling problem
- Adaptive feasible and infeasible tabu search for weighted vertex coloring
- An exact algorithm for the partition coloring problem
- Models and heuristic algorithms for a weighted vertex coloring problem
- On the benchmark instances for the bin packing problem with conflicts
- Maximum-weight stable sets and safe lower bounds for graph coloring
- Iterated local search with tabu search for the weighted vertex coloring problem
- A note on selective line-graphs and partition colorings
- Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation
- Reducing hypergraph coloring to clique search
This page was built for publication: Solving vertex coloring problems as maximum weight stable set problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q516805)
