Color Permutation Problem (Jun-Dong Cho)
Thu, 5 Nov 1992 17:20:20 GMT

          From comp.compilers

Related articles
Graph Coloring Problem (1992-10-24)
Re: Graph Coloring Problem (1992-10-28)
Color Permutation Problem (1992-11-05)
| List of all articles for this month |

Newsgroups: comp.compilers,comp.theory
From: (Jun-Dong Cho)
Organization: EECS Department, Northwestern University
Date: Thu, 5 Nov 1992 17:20:20 GMT
References: 92-10-093 92-10-112
Keywords: theory, question

Dear netters,

Given a complete graph G = (V,E) with edge-weighted,
(colors 1, 2, ..., n are already assigned to nodes 1, 2, ..., n in G)
I want to minimze the following function,
by permuting colors assigned to nodes,

  \sum_{(i,j) \in E} w_{i,j}/|C_{i} - C_{j}|

where w_{i,j} is the edge weight (positive integer) between nodes i and j,
and C_{i} is a color assigned to vertex i.

Is the problem proven to be NP-hard?

Jun-Dong Cho | Email:
Department of EECS |
Northwestern University |
Evanston, IL 60208 |

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.