A heuristic for the minimum cost chromatic partition problem
| Autor: | Philippe L. F. dos Santos, Celso C. Ribeiro |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Very-large-scale integration
021103 operations research Computer science ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION 0211 other engineering and technologies Partition problem 02 engineering and technology Management Science and Operations Research Graph Computer Science Applications Theoretical Computer Science Vertex (geometry) Combinatorics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Trajectory search Chromatic scale Graph coloring Metaheuristic ComputingMethodologies_COMPUTERGRAPHICS MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | RAIRO - Operations Research. 54:845-871 |
| ISSN: | 1290-3868 0399-0559 |
| Popis: | The graph coloring problem consists in coloring the vertices of a graph G=(V, E) with a minimum number of colors, such as that any two adjacent vertices receive different colors. The minimum cost chromatic partition problem (MCCPP) is an extension of the graph coloring problem in which there are costs associated with the colors and one seeks a vertex coloring minimizing the sum of the costs of the colors used in each vertex. The problem finds applications in VLSI design and in some scheduling problems modeled on interval graphs. We propose a trajectory search heuristic using local search, path-relinking, and perturbations for solving MCCPP and discuss computational results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|