An efficient algorithm for finding maximum cycle packings in reducible flow graphs

被引：0

作者：

Chen, XJ ^{[1
]}

Zang, W ^{[1
]}

机构：

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

来源：

ALGORITHMS AND COMPUTATION | 2004年 / 3341卷

关键词：

feedback set; cycle packing; network flow; algorithm; complexity;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Reducible flow graphs occur naturally in connection with flow-charts of computer programs and are used extensively for code optimization and global data flow analysis. In this paper we present an O(n(2)mlog(n(2)/m)) algorithm for finding a maximum cycle packing in any weighted reducible flow graph with n vertices and m arcs.

引用

页码：306 / 317

页数：12

共 50 条

[1] An Efficient Algorithm for Finding Maximum Cycle Packings in Reducible Flow Graphs
Xujin Chen
Wenan Zang
Algorithmica, 2006, 44 : 195 - 211
[2] An efficient algorithm for finding maximum cycle packings in reducible flow graphs
Chen, XJ
Zang, WN
ALGORITHMICA, 2006, 44 (03) : 195 - 211
[3] On maximum cycle packings in polyhedral graphs
Recht, Peter
Stehling, Stefan
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2014, 2 (01) : 18 - 31
[4] A PARALLEL ALGORITHM FOR FINDING MINIMUM CUTSETS IN REDUCIBLE GRAPHS
DEKEL, E
HU, J
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1994, 20 (01) : 43 - 55
[5] LINEAR TIME ALGORITHM FOR FINDING MINIMUM CUTSETS IN REDUCIBLE GRAPHS
SHAMIR, A
SIAM JOURNAL ON COMPUTING, 1979, 8 (04) : 645 - 655
[6] EFFICIENT ALGORITHMS FOR FINDING MAXIMUM MATCHING IN GRAPHS
GALIL, Z
COMPUTING SURVEYS, 1986, 18 (01) : 23 - 38
[7] An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs
Mrinmoy Hota
Madhumangal Pal
Tapan K. Pal
Computational Optimization and Applications, 2001, 18 : 49 - 62
[8] FINDING A MINIMUM FEEDBACK ARC SET IN REDUCIBLE FLOW-GRAPHS
RAMACHANDRAN, V
JOURNAL OF ALGORITHMS, 1988, 9 (03) : 299 - 313
[9] An efficient algorithm for finding a maximum weight k-independent set on trapezoid graphs
Hota, M
Pal, M
Pal, TK
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2001, 18 (01) : 49 - 62
[10] EFFICIENT ALGORITHMS FOR FINDING MAXIMUM MATCHING IN GRAPHS.
Galil, Zvi
Computing surveys, 1986, 18 (01): : 23 - 38

← 1 2 3 4 5 →