An efficient algorithm for minimum feedback vertex sets in rotator graphs |
| |
Authors: | Chi-Jung Kuo Hon-Ren Lin |
| |
Affiliation: | a Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan, ROC b Department of Information Management, National Taipei College of Business, Taipei, Taiwan, ROC |
| |
Abstract: | For a rotator graph with n! nodes, Hsu and Lin [C.C. Hsu, H.R. Lin, H.C. Chang, K.K. Lin, Feedback Vertex Sets in Rotator Graphs, in: Lecture Notes in Comput. Sci., vol. 3984, 2006, pp. 158-164] first proposed an algorithm which constructed a feedback vertex set (FVS) with time complexity O(nn−3). In addition, they found that the size of the FVS is n!/3, which was proved to be minimum. In this paper, we present an efficient algorithm which constructs an FVS for a rotator graph in O(n!) time and also obtains the minimum FVS size n!/3. In other words, this algorithm derives the optimal result with linear time complexity in terms of the number of nodes in the rotator graph. |
| |
Keywords: | Feedback vertex set Rotator graph Generator Cycle Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|