An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
From MaRDI portal
Publication:2029946
Abstract: We consider the selective graph coloring problem, which is a generalization of the classical graph coloring problem. Given a graph together with a partition of its vertex set into clusters, we want to choose exactly one vertex per cluster so that the number of colors needed to color the selected set of vertices is minimized. This problem is known to be NP-hard. In this study, we focus on an exact cutting plane algorithm for selective graph coloring in perfect graphs. Since there exists no suite of perfect graph instances to the best of our knowledge, we also propose an algorithm to randomly (but not uniformly) generate perfect graphs, and provide a large collection of instances available online. We conduct computational experiments to test our method on graphs with varying size and densities, and compare our results with a state-of-the-art algorithm from the literature and with solving an integer programming formulation of the problem by CPLEX. Our experiments demonstrate that our solution strategy significantly improves the solvability of the problem.
Recommendations
- On some applications of the selective graph coloring problem
- On the complexity of the selective graph coloring problem in some special classes of graphs
- On the minimum and maximum selective graph coloring problems in some graph classes
- An exact approach for the vertex coloring problem
- Selective graph coloring in some special classes of graphs
Cites work
- A branch-and-cut algorithm for graph coloring
- A branch-and-cut algorithm for partition coloring
- A branch-and-price approach for the partition coloring problem
- A Column Generation Approach for Graph Coloring
- A Combinatorial Decomposition Theory
- A review on algorithms for maximum clique problems
- A simple and faster branch-and-bound algorithm for finding a maximum clique
- A survey on vertex coloring problems
- Algorithmic graph theory and perfect graphs
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- An exact algorithm for the partition coloring problem
- Classes of perfect graphs
- Efficient graph representations
- Experimental and Efficient Algorithms
- Geometric algorithms and combinatorial optimization
- Graph Classes: A Survey
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 3887730 (Why is no real title available?)
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 3869356 (Why is no real title available?)
- scientific article; zbMATH DE number 3878985 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 3400923 (Why is no real title available?)
- Improving Discrete Model Representations via Symmetry Considerations
- Linear-time generation of random chordal graphs
- Maximum-weight stable sets and safe lower bounds for graph coloring
- Normal hypergraphs and the perfect graph conjecture
- On extracting maximum stable sets in perfect graphs using Lovász's theta function
- On some applications of the selective graph coloring problem
- On the Lovász theta function and some variants
- On the Shannon capacity of a graph
- Recognizing Berge graphs
- The ellipsoid method and its consequences in combinatorial optimization
- The sandwich theorem
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- The strong perfect graph theorem
- The structure of bull-free perfect graphs
- Two methods for the generation of chordal graphs
Cited in
(3)
This page was built for publication: An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029946)
