DocumentCode
3013181
Title
A distributed algorithm for finding minimal feedback vertex sets in directed split-stars
Author
Wang, Fu Hsing ; Hsu, Cheng Ru
Author_Institution
Dept. of Inf. Manage., Chungyu Inst. of Technol., Keelung, Taiwan
fYear
2004
fDate
10-12 May 2004
Firstpage
174
Lastpage
179
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 minimal feedback vertex sets of directed split-stars. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for directed split-stars. Moreover, a simple distributed algorithm is presented for finding such sets.
Keywords
computational complexity; directed graphs; distributed algorithms; feedback; multiprocessor interconnection networks; NP hard problem; acyclic subgraph; directed split-stars; distributed algorithm; minimal feedback vertex sets; Approximation algorithms; Bipartite graph; Distributed algorithms; Feedback; Hypercubes; Information management; Polynomials; System recovery; Terminology; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on
ISSN
1087-4089
Print_ISBN
0-7695-2135-5
Type
conf
DOI
10.1109/ISPAN.2004.1300477
Filename
1300477
Link To Document