The feedback vertex set (FVS) problem can be stated as follows: Given a directed graph G(V,E), where V denotes the set of n vertices and E the set of arcs, find a minimum cardinality subset V' of V such that every directed cycle in G contains at least one vertex in V'. In other words, we wish to determine how to remove the minimum number of vertices from the original graph such that the resulting graph has no directed cycle.

In this talk, we present a survey of recent heuristics for the FVS, including a Greedy Randomized Adaptive Search Procedure (GRASP) which can be easily parallelized.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing