Combinatorial algorithms for feedback problems in directed graphs

被引：34

作者：

Demetrescu, C

Finocchi, I

机构：

[1] Univ Roma La Sapienza, Dipartimento Informat & Sistemist, I-00198 Rome, Italy

[2] Univ Roma Tor Vergata, Dipartimento Informat Sistemi & Prod, I-00133 Rome, Italy

来源：

INFORMATION PROCESSING LETTERS | 2003年 / 86卷 / 03期

关键词：

approximation algorithms; combinatorial optimization; feedback problems; directed graphs;

D O I：

10.1016/S0020-0190(02)00491-X

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given a weighted directed graph G = (V, A), the minimum feedback arc set problem consists of finding a minimum weight set of arcs A' subset of or equal to 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. (C) 2003 Elsevier Science B.V. All rights reserved.

引用

页码：129 / 136

页数：8

共 23 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

BAFNA V, 1995, LECT NOTES COMPUTER, V1004, P142

[3] Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference [J].