Solving vertex coloring problems as maximum weight stable set problems
From MaRDI portal
Publication:516805
DOI10.1016/j.dam.2016.09.018zbMath1358.05098OpenAlexW2526286943WikidataQ57659018 ScholiaQ57659018MaRDI QIDQ516805
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
Related Items
An exact algorithm for the partition coloring problem, On Monte Carlo tree search for weighted vertex coloring, Iterated local search with tabu search for the weighted vertex coloring problem, An exact algorithm for the edge coloring by total labeling problem, Reducing hypergraph coloring to clique search, Monte Carlo tree search with adaptive simulation: a case study on weighted vertex coloring, Adaptive feasible and infeasible tabu search for weighted vertex coloring, A branch-and-cut algorithm for the edge interdiction clique problem, A note on selective line-graphs and partition colorings, On the benchmark instances for the bin packing problem with conflicts
Cites Work
- Lower bounding techniques for DSATUR-based branch and bound
- An exact approach for the vertex coloring problem
- Exact weighted vertex coloring via branch-and-price
- A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
- An introduction to timetabling
- Models and heuristic algorithms for a weighted vertex coloring problem
- A fast algorithm for the maximum clique problem
- A new \textsf{DSATUR}-based algorithm for exact vertex coloring
- Maximum-weight stable sets and safe lower bounds for graph coloring
- A note on the Cornaz-Jost transformation to solve the graph coloring problem
- A polyhedral approach for the equitable coloring problem
- Chromatic Gallai identities operating on Lovász number
- On the asymmetric representatives formulation for the vertex coloring problem
- A branch-and-cut algorithm for graph coloring
- A one-to-one correspondence between colorings and stable sets
- Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
- Algorithms for the Bin Packing Problem with Conflicts
- A Branch-and-Price Algorithm for the Bin Packing Problem with Conflicts
- A survey on vertex coloring problems
- A graph coloring algorithm for large scheduling problems
- New methods to color the vertices of a graph
