MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS

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...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2012-06, Vol.23 (4), p.931-940
Main Authors: KUO, CHI-JUNG, HSU, CHIUN-CHIEH, LIN, HON-REN, CHEN, DA-REN
Format: Article
Language:English
Subjects:
Algorithms
Feedback
Foundations
Graphs
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 FVS 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.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054112500116