home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / compiler / 1836 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  1.4 KB
  1. Xref: sparky comp.compilers:1836 comp.theory:2387
  2. Path: sparky!uunet!ogicse!das-news.harvard.edu!spdcc!iecc!compilers-sender
  3. From: jdcho@karachi.eecs.nwu.edu (Jun-Dong Cho)
  4. Newsgroups: comp.compilers,comp.theory
  5. Subject: Color Permutation Problem
  6. Keywords: theory, question
  7. Message-ID: <92-11-027@comp.compilers>
  8. Date: 5 Nov 92 17:20:20 GMT
  9. Article-I.D.: comp.92-11-027
  10. References: <92-10-093@comp.compilers> <92-10-112@comp.compilers>
  11. Sender: compilers-sender@iecc.cambridge.ma.us
  12. Reply-To: jdcho@karachi.eecs.nwu.edu (Jun-Dong Cho)
  13. Organization: EECS Department, Northwestern University
  14. Lines: 23
  15. Approved: compilers@iecc.cambridge.ma.us
  16.  
  17. Dear netters,
  18.  
  19. Given a complete graph G = (V,E) with edge-weighted,
  20. (colors 1, 2, ..., n  are already assigned to nodes 1, 2, ..., n in G)
  21. I want to minimze the following function,
  22. by permuting colors assigned to nodes,  
  23.  
  24.  \sum_{(i,j) \in E} w_{i,j}/|C_{i} - C_{j}|
  25.  
  26. where w_{i,j} is the edge weight (positive integer) between nodes i and j,
  27. and C_{i} is a color assigned to vertex i. 
  28.  
  29. Is the problem proven to be NP-hard?
  30.  
  31. Email: jdcho@eecs.nwu.edu 
  32. -- 
  33. Jun-Dong Cho                 |   Email: jdcho@eecs.nwu.edu
  34. Department of EECS           |
  35. Northwestern University      |
  36. Evanston, IL 60208           |
  37. -- 
  38. Send compilers articles to compilers@iecc.cambridge.ma.us or
  39. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  40.