Title: Combinatorial algorithms for feedback problems in directed graphs
Abstract: Given a weighted directed graph G=(V,A), the minimum feedback arc set problem consists of finding a minimum weight set of arcs A′⊆A such that the directed graph (V,A⧹A′) is acyclic. Similarly, the minimum feedback vertex set problem consists of finding a minimum weight set of vertices containing at least one vertex for each directed cycle. Both problems are NP-complete. We present simple combinatorial algorithms for these problems that achieve an approximation ratio bounded by the length, in terms of number of arcs, of a longest simple cycle of the digraph.
Publication Year: 2003
Publication Date: 2003-05-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 46
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot