Name
Abstract | ||
|---|---|---|
This paper provides an algorithm for finding feedback vertex set in rotator graphs. Feedback vertex set is a subset of a graph whose removal causes an acyclic graph and is developed in various topologies of interconnected networks. In 1992, Corbett pioneered rotator graphs, whose interesting topological structures attract many researchers to publish relative papers in recent years. In this paper, we first develops feedback vertex set algorithm for rotator graphs. Our algorithm utilizes the technique of dynamic programming and generates a feedback vertex set of size n!/3 for a rotator graph of scale n, which contains n! nodes. The generated set size is proved to be minimum. Finding a minimum feedback vertex set is a NP-hard problem for general graphs. The time complexity of our algorithm, which finds a minimum feedback vertex set for a rotator graph of scale n, is proved to be O(nn−−3). |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11751649_17 | ICCSA (5) |
Keywords | Field | DocType |
general graph,acyclic graph,feedback vertex set,feedback vertex,scale n,minimum feedback vertex,feedback vertex set algorithm,rotator graph,size n,minimum feedback vertex set,time complexity,np hard problem | Discrete mathematics,Combinatorics,Computer science,Vertex (graph theory),Neighbourhood (graph theory),Cycle graph,Independent set,Vertex cover,Feedback arc set,Feedback vertex set,Maximal independent set | Conference |
Volume | ISSN | ISBN |
3984 | 0302-9743 | 3-540-34079-3 |
Citations | PageRank | References |
4 | 0.46 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chiun-Chieh Hsu | 1 | 132 | 18.37 |
| Hon-ren Lin | 2 | 11 | 1.65 |
| Hsi-Cheng Chang | 3 | 24 | 2.38 |
| Kung-Kuei Lin | 4 | 11 | 0.97 |