|
|||||
|
|
Feedback vertex sets in star graphs |
|
| Authors: | Fu-Hsing Wang Yue-Li Wang Jou-Ming Chang |
| Affiliation: | a Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan, Republic of China b Department of Information Management, National Taipei College of Business, Taipei, Taiwan, Republic of China c Department of Information Management, Chung Yu Junior College of Business Administration, Keelung, Taiwan, Republic of China |
| Abstract: | In a graph G=(V,E), a subset F⊂V(G) is a feedback vertex set of G if the subgraph induced by V(G)?F is acyclic. In this paper, we propose an algorithm for finding a small feedback vertex set of a star graph. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for star graphs. Also by applying the properties of regular graphs, a lower bound can easily be achieved for star graphs. |
| Keywords: | Feedback vertex sets Interconnection networks Star graphs Algorithms Analysis of algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |