Article View: comp.theory
Article #1776Feedback vertex set problem
From: Peter Shor
Date: Mon, 03 Jun 1991 21:06
Date: Mon, 03 Jun 1991 21:06
16 lines
918 bytes
918 bytes
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
Technical Details
Message-ID:
<9106032106.AA12780@irt.watson.ibm.com>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!ucbvax!RESEARCH.ATT.COM!shorShow Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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 <shor%research.att.com@VM1.NoDak.EDU> Lines: 16