Parallel Heuristics for the Feedback Vertex Set Problem

Friday, May 16, 1997 - 11:00am - 12:00pm
Vincent 570
Panos Pardalos (University of Florida)
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.