home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1820 < prev    next >
Encoding:
Text File  |  1992-08-25  |  1.4 KB  |  32 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!watson!norway.fishkill.ibm.com!raghu
  3. From: raghu@norway.fishkill.ibm.com (Raghu Hudli)
  4. Subject: Is this problem NP-complete?
  5. Sender: @watson.ibm.com
  6. Message-ID: <1992Aug25.185050.11956@watson.ibm.com>
  7. Date: Tue, 25 Aug 92 18:50:50 GMT
  8. Reply-To: raghu@vnet.ibm.com
  9. Organization: IBM Corp., E. Fishkill, NY
  10. Lines: 20
  11.  
  12. The problem is given a weighted graph G = (V,E) with positive weights
  13. for all edges in E, the weight of a vertex v_i in V is defined as the
  14. sum of the weights of edges incident on v_i. Find a subset S of V, such
  15. that |S| = K and the graph G' = ((V-S), E') has no vertex whose weight 
  16. is greater than a constant T. E' is  E - edges incident on vertices in S.
  17.  
  18. I have heuristic solutions for the problem that seem to work well. I wanted
  19. to make sure that I was not missing the optimum solution if the problem were
  20. not NP-complete. 
  21.  
  22. Thanks in advance for your response.
  23.  
  24. Raghu Hudli
  25. -----------------------------------------------------------------------
  26. Raghu V. Hudli                       Tel:   (914) 892-4188
  27. IBM Corporation                      Fax:   (914) 892-4316 
  28. E. Fishkill, NY                      email: raghu@vnet.ibm.com
  29. ------------------------------------------------------------------------
  30. Disclaimer: The opinions/views expressed here are mine and my employer
  31. does not necessarily concur with me.
  32.