home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / 2341 < prev    next >
Encoding:
Internet Message Format  |  1992-11-06  |  1.1 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!sjha
  2. From: sjha+@cs.cmu.edu (Somesh Jha)
  3. Newsgroups: comp.theory
  4. Subject: Elimination ordering question.
  5. Message-ID: <Bx984q.220.2@cs.cmu.edu>
  6. Date: 5 Nov 92 17:48:25 GMT
  7. Article-I.D.: cs.Bx984q.220.2
  8. Sender: news@cs.cmu.edu (Usenet News System)
  9. Organization: School of Computer Science, Carnegie Mellon
  10. Lines: 18
  11. Nntp-Posting-Host: gs62.sp.cs.cmu.edu
  12.  
  13.  
  14.  
  15. Hi:
  16.  
  17. I need some  literature on the following problem. I already have a proof that
  18. it is NP-complete. Given a family of sets which are subsets of 
  19. {x_1,x_2, ... ,x_n}. I define what it means to eliminate x_i. 
  20. We union together all the sets which contain x_i, remove x_i from it,
  21. and replace all these sets by the new set. Now we get a new family of
  22. sets. The problem is to find the best elimination ordering. Or the
  23. decision version will be to find an elimination ordering so that we
  24. do not create a set of size greater that k during the elimination
  25. procedure.
  26.  
  27. Any pointers? I know the problem is vague, but still I am hoping somebody
  28. must have worked on a similar problem.
  29.  
  30. Thanks.
  31.