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 条
  • [21] Efficient Local Search for Maximum Weight Cliques in Large Graphs
    Fan, Yi
    Ma, Zongjie
    Su, Kaile
    Li, Chengqian
    Rao, Cong
    Liu, Ren-Hau
    Latecki, Longin Jan
    2017 IEEE 29TH INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI 2017), 2017, : 1099 - 1104
  • [22] Efficient Maximum Clique Computation over Large Sparse Graphs
    Chang, Lijun
    KDD'19: PROCEEDINGS OF THE 25TH ACM SIGKDD INTERNATIONAL CONFERENCCE ON KNOWLEDGE DISCOVERY AND DATA MINING, 2019, : 529 - 538
  • [23] An Efficient Local Search for the Maximum Clique Problem on Massive Graphs
    Kanahara, Kazuho
    Oda, Tetsuya
    Kulla, Elis
    Uejima, Akira
    Katayama, Kengo
    ADVANCES IN INTERNET, DATA & WEB TECHNOLOGIES (EIDWT-2022), 2022, 118 : 201 - 211
  • [24] USE OF DYNAMIC TREES IN A NETWORK SIMPLEX ALGORITHM FOR THE MAXIMUM FLOW PROBLEM
    GOLDBERG, AV
    GRIGORIADIS, MD
    TARJAN, RE
    MATHEMATICAL PROGRAMMING, 1991, 50 (03) : 277 - 290
  • [25] Tabu search with graph reduction for finding maximum balanced bicliques hock for in bipartite graphs
    Zhou, Yi
    Hao, Jin-Kao
    ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2019, 77 : 86 - 97
  • [26] Efficient algorithms for finding a tree 3-spanner on permutation graphs
    Chen, HC
    Wu, SH
    Yang, CB
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2003, E86D (11) : 2390 - 2394
  • [27] Efficient Branch and Bound Motif Finding with Maximum Accuracy based on Hashing
    Soundarajan, Sanjay
    Salomon, Michelle
    Park, Jin H.
    2019 IEEE 9TH ANNUAL COMPUTING AND COMMUNICATION WORKSHOP AND CONFERENCE (CCWC), 2019, : 866 - 872
  • [28] EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
    Bonamy, Marthe
    Bonnet, Edouard
    Bousquet, Nicolas
    Charbit, Pierre
    Giannopoulos, Panos
    Kim, Eun Jung
    Rzazewski, Pawel
    Sikora, Florian
    Thomasse, Stephan
    JOURNAL OF THE ACM, 2021, 68 (02)
  • [29] A linear algorithm for maximum weight cliques in proper circular arc graphs
    Bhattacharya, B
    Hell, P
    Huang, J
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (02) : 274 - 289
  • [30] A linear algorithm to find the maximum-weighted matching in halin graphs
    Lu, Yunting
    Li, Yueping
    Lou, Dingjun
    IMECS 2007: INTERNATIONAL MULTICONFERENCE OF ENGINEERS AND COMPUTER SCIENTISTS, VOLS I AND II, 2007, : 2274 - +
12345