Packing feedback arc sets in reducible flow graphs

被引：1

作者：

Xiao, Han ^{[1
]}

机构：

[1] Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2016年 / 32卷 / 03期

关键词：

Min-max relation; Feedback arc set; Packing; Reducible flow graph; Algorithm; ALGORITHM;

D O I：

10.1007/s10878-015-9922-6

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper we establish a min-max relation in arc-weighted reducible flow graphs. In particular, we prove that the maximum cardinality of feedback arc set packings equals the minimum total weight of cycles. We also present an algorithm for finding a maximum feedback arc set packing in reducible flow graphs.

引用

页码：951 / 959

页数：9

共 11 条

[1] Ahuja RK, 1993, Network flows
[2] An efficient algorithm for finding maximum cycle packings in reducible flow graphs
Chen, XJ
Zang, WN
[J]. ALGORITHMICA, 2006, 44 (03) : 195 - 211
[3] Frank A, 1976, PROBLEMES COMBINATOI, V260, P157
[4] Hecht M. S., 1972, SIAM Journal on Computing, V1, P188, DOI 10.1137/0201014
[5] CHARACTERIZATIONS OF REDUCIBLE FLOW GRAPHS
HECHT, MS
ULLMAN, JD
[J]. JOURNAL OF THE ACM, 1974, 21 (03) : 367 - 375
[6] Hecht MS., 1977, FLOW ANAL COMPUTER P
[7] Hopcroft J.E., 1972, P 6 ANN PRINCETON C, P119
[8] A MINIMAX ARC THEOREM FOR REDUCIBLE FLOW-GRAPHS
RAMACHANDRAN, V
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (04) : 554 - 560
[9] FINDING A MINIMUM FEEDBACK ARC SET IN REDUCIBLE FLOW-GRAPHS
RAMACHANDRAN, V
[J]. JOURNAL OF ALGORITHMS, 1988, 9 (03) : 299 - 313
[10] LINEAR TIME ALGORITHM FOR FINDING MINIMUM CUTSETS IN REDUCIBLE GRAPHS
SHAMIR, A
[J]. SIAM JOURNAL ON COMPUTING, 1979, 8 (04) : 645 - 655

← 1 2 →