MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS

被引：0

作者：

Kuo, Chi-Jung ^{[1
]}

Hsu, Chiun-Chieh ^{[1
]}

Lin, Hon-Ren ^{[2
]}

Chen, Da-Ren ^{[3
]}

机构：

[1] Natl Taiwan Univ Sci & Technol, Dept Informat Management, Taipei, Taiwan

[2] Natl Taipei Coll Business, Dept Informat Management, Taipei, Taiwan

[3] Natl Taichung Univ Sci & Technol, Dept Informat Management, Taichung, Taiwan

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2012年 / 23卷 / 04期

关键词：

Feedback arc set; rotator graph; incomplete rotator graph; generator; directed cycle; VERTEX SETS; ALGORITHM; MESHES; STAR;

D O I：

10.1142/S0129054112500116

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A feedback vertex/arc set (abbreviated as FVS/FAS) of a graph is a subset of the vertices/arcs which contains at least one vertex/arc for every cycle of that graph. A minimum FVS/FAS is an FVS/FAS which contains the smallest number of vertices/arcs. Hsu et al. [11] first proposed an algorithm which can find a minimum FA'S in a rotator graph. In this paper, we present a formula for finding an FAS for a rotator graph and prove that the FAS is minimum. This formula can be easily implemented by an efficient algorithm which obtains a minimum FAS in a rotator graph. Finally, we also present a concise formula for finding a minimum FAS in an incomplete rotator graph in this paper.

引用

页码：931 / 940

页数：10

共 50 条

[1] An efficient algorithm for minimum feedback vertex sets in rotator graphs
Kuo, Chi-Jung
Hsu, Chiun-Chieh
Lin, Hon-Ren
Lin, Kung-Kuei
INFORMATION PROCESSING LETTERS, 2009, 109 (09) : 450 - 453
[2] Feedback vertex sets in rotator graphs
Hsu, CC
Lin, HR
Chang, HC
Lin, KK
COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2006, PT 5, 2006, 3984 : 158 - 164
[3] Tight Upper Bounds for Minimum Feedback Arc Sets of Regular Graphs
Hanauer, Kathrin
Brandenburg, Franz J.
Auer, Christopher
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2013, 2013, 8165 : 298 - 309
[4] COMMENT ON MINIMUM FEEDBACK ARC SETS
LAWLER, EL
IEEE TRANSACTIONS ON CIRCUIT THEORY, 1964, CT11 (02): : 296 - &
[5] On Minimum Feedback Vertex Sets in Graphs
Takaoka, Asahi
Tayu, Satoshi
Ueno, Shuichi
2012 THIRD INTERNATIONAL CONFERENCE ON NETWORKING AND COMPUTING (ICNC 2012), 2012, : 429 - 434
[6] MINIMUM FEEDBACK ARC SETS FOR A DIRECTED GRAPH
YOUNGER, DH
IEEE TRANSACTIONS ON CIRCUIT THEORY, 1963, CT10 (02): : 238 - &
[7] ON DETERMINATION OF MINIMUM FEEDBACK ARC AND VERTEX SETS
DIVIETI, L
GRASSELLI, A
LEMPEL, A
CEDERBAUM, I
IEEE TRANSACTIONS ON CIRCUIT THEORY, 1968, CT15 (01): : 86 - +
[8] Incomplete Rotator Cable Did Not Cause Rotator Cuff Dysfunction in Case of Rotator Cuff Tear: A Biomechanical Study of the Relationship Between Rotator Cable Integrity and Rotator Cuff Function
Wang, Liren
Kang, Yuhao
Xie, Guoming
Cai, Jiangyu
Chen, Chang'an
Yan, Xiaoyu
Jiang, Jia
Zhao, Jinzhong
ARTHROSCOPY-THE JOURNAL OF ARTHROSCOPIC AND RELATED SURGERY, 2021, 37 (08): : 2444 - 2451
[9] MINIMUM FEEDBACK ARC AND VERTEX SETS OF A DIRECTED GRAPH
LEMPEL, A
CEDERBAUM, I
IEEE TRANSACTIONS ON CIRCUIT THEORY, 1966, CT13 (04): : 399 - +
[10] Minimum feedback node sets in trivalent Cayley graphs
Suzuki, Y
Kaneko, K
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2003, E86D (09): : 1634 - 1636

← 1 2 3 4 5 →