home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / ai / neuraln / 3344 < prev    next >
Encoding:
Internet Message Format  |  1992-08-29  |  1.4 KB
  1. Path: sparky!uunet!gatech!usenet.ins.cwru.edu!ukma!rutgers!ub!acsu.buffalo.edu!jagota
  2. From: jagota@sybil.cs.Buffalo.EDU (Arun Jagota)
  3. Newsgroups: comp.ai.neural-nets
  4. Subject: seeking refs: vertex cover using NNs
  5. Message-ID: <BtptEu.6Cs@acsu.buffalo.edu>
  6. Date: 28 Aug 92 22:35:17 GMT
  7. Sender: nntp@acsu.buffalo.edu
  8. Organization: State University of New York at Buffalo/Comp Sci
  9. Lines: 14
  10. Originator: jagota@sybil.cs.Buffalo.EDU
  11. Nntp-Posting-Host: sybil.cs.buffalo.edu
  12.  
  13. I am seeking references on application of neural networks to the vertex
  14. cover (MVC) graph optimization problem. I am aware of one encoding of MVC (
  15. TR208/88; U. Toronto; 1988) in a Hopfield net; though this encoding is only
  16. for complexity theory purposes. Scanning the TOC of the book: 
  17. Neural Networks for Parallel Computing, Y. Takefuji does not show MVC was
  18. addressed. Also, vertex cover is apparently mentioned only in one line in the 
  19. book: Simulated Annealing and Boltzmann Machines - A Stochastic Approach to
  20. Combinatorial Optimization and Neural Computing, E. Aarts & J. Korst. 
  21. One reason may be that MVC may be indirectly solved (approximated) via 
  22. approximation to maximum clique, maximum independent set, etc. I have 
  23. references to these; I am looking for _direct_ solution of MVC. 
  24.    Please e-mail references directly; encoding details would be even more
  25. appreciated. I will e-mail out what I collect upon request.
  26. Thanks in advance,  Arun Jagota     jagota@cs.buffalo.edu
  27.