Color Permutation Problem

jdcho@karachi.eecs.nwu.edu (Jun-Dong Cho)
Thu, 5 Nov 1992 17:20:20 GMT

          From comp.compilers
Related articles
Graph Coloring Problem dahl@ee.umn.edu (1992-10-24)
Re: Graph Coloring Problem cliffc@rice.edu (1992-10-28)
Color Permutation Problem jdcho@karachi.eecs.nwu.edu (1992-11-05)
| List of all articles for this month |
Newsgroups: comp.compilers,comp.theory
From: jdcho@karachi.eecs.nwu.edu (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?


Email: jdcho@eecs.nwu.edu
--
Jun-Dong Cho | Email: jdcho@eecs.nwu.edu
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.