Main navigation | Main content

HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program

PROGRAMS/ACTIVITIES

Annual Thematic Program »Postdoctoral Fellowships »Hot Topics and Special »Public Lectures »New Directions »PI Programs »Math Modeling »Seminars »Be an Organizer »Annual »Hot Topics »PI Summer »PI Conference »Applying to Participate »

Talk Abstract

Parallel Heuristics for the Feedback Vertex Set Problem

Parallel Heuristics for the Feedback Vertex Set Problem

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