Thu, 5 Nov 1992 17:20:20 GMT

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) |

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.