Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!ucbvax!RESEARCH.ATT.COM!shor From: shor@RESEARCH.ATT.COM (Peter Shor) Newsgroups: comp.theory Subject: Feedback vertex set problem Message-ID: <9106032106.AA12780@irt.watson.ibm.com> Date: 3 Jun 91 21:06:27 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Peter Shor Lines: 16 I'm interested in heuristics for the feedback vertex set problem. This problem is: given a directed graph, remove as few vertices as possible so as to break all cycles. I'm also interested in a variation of this problem, where the nodes are colored, and if you remove one node of a given color, you must remove them all. Does anyone have pointers to good heuristics? Thanks, Peter Shor AT&T Bell Labs 600 Mountain Ave, Rm. 2D-149 Murray Hill, NJ 07974 shor@research.att.com