An efficient algorithm for minimum feedback vertex sets in rotator graphs

被引：9

作者：

Kuo, Chi-Jung ^{[1
]}

Hsu, Chiun-Chieh ^{[1
]}

Lin, Hon-Ren ^{[2
]}

Lin, Kung-Kuei ^{[1
]}

机构：

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

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

来源：

INFORMATION PROCESSING LETTERS | 2009年 / 109卷 / 09期

关键词：

Feedback vertex set; Rotator graph; Generator; Cycle; Graph algorithms; APPROXIMATION ALGORITHMS; BUTTERFLIES; NETWORKS; MESHES;

D O I：

10.1016/j.ipl.2009.01.004

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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(n(n-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. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：450 / 453

页数：4

共 14 条

[1] Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference [J].

Bar-Yehuda, R ;

Geiger, D ;

Naor, J ;

Roth, RM .

SIAM JOURNAL ON COMPUTING, 1998, 27 (04) :942-959

[2] New bounds on the size of the minimum feedback vertex set in meshes and butterflies [J].

Caragiannis, I ;

Kaklamanis, C ;

Kanellopoulos, P .

INFORMATION PROCESSING LETTERS, 2002, 83 (05) :275-280

[3] ROTATOR GRAPHS - AN EFFICIENT TOPOLOGY FOR POINT-TO-POINT MULTIPROCESSOR NETWORKS [J].

CORBETT, PF .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1992, 3 (05) :622-626

[4] EXACT AND HEURISTIC ALGORITHMS FOR THE WEIGHTED FEEDBACK ARC SET PROBLEM - A SPECIAL CASE OF THE SKEW-SYMMETRIC QUADRATIC ASSIGNMENT PROBLEM [J].

FLOOD, MM .

NETWORKS, 1990, 20 (01) :1-23

[5] Feedback vertex set in hypercubes [J].

Focardi, R ;

Luccio, FL ;

Peleg, D .

INFORMATION PROCESSING LETTERS, 2000, 76 (1-2) :1-5

[6]

Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness

[7] A GRAPH THEORETIC APPROACH TO STATISTICAL-DATA SECURITY [J].

GUSFIELD, D .

SIAM JOURNAL ON COMPUTING, 1988, 17 (03) :552-571

[8]

Hsu CC, 2006, LECT NOTES COMPUT SC, V3984, P158

[9] APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS [J].

JOHNSON, DS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (03) :256-278

[10] Minimum feedback vertex sets in shuffle-based interconnection networks [J].

Královic, R ;

Ruzicka, P .

INFORMATION PROCESSING LETTERS, 2003, 86 (04) :191-196

← 1 2 →