Combinatorial algorithms for feedback problems in directed graphs |
| |
Authors: | Camil Demetrescu |
| |
Affiliation: | a Dipartimento di Informatica e Sistemistica, Università degli Studi di Roma “La Sapienza”, Via Salaria 113, 00198 Roma, Italy b Dipartimento di Informatica, Sistemi e Produzione, Università degli Studi di Roma “Tor Vergata”, Via di Tor Vergata 110, 00133 Roma, Italy |
| |
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. |
| |
Keywords: | Approximation algorithms Combinatorial optimization Feedback problems Directed graphs |
本文献已被 ScienceDirect 等数据库收录! |
|