Minimum feedback vertex sets in shuffle-based interconnection networks |
| |
Authors: | Rastislav Krá lovi?,Peter Ru?i?ka |
| |
Affiliation: | a Department of Computer Science, Comenius University, Bratislava, Slovak Republic b Institute of Informatics, Comenius University, Bratislava, Slovak Republic |
| |
Abstract: | Given a graph G, the problem is to construct a smallest subset S of vertices whose deletion results in an acyclic subgraph. The set S is called a minimum feedback vertex set for G.Tight upper and lower bounds on the cardinality of minimum feedback vertex sets have been previously obtained for some hypercube-like networks, such as meshes, tori, butterflies, cube-connected cycles and hypercubes. In this paper we construct minimum feedback vertex sets and determine their cardinalities in certain shuffle-based interconnection networks, such as shuffle-exchange, de Bruijn and Kautz networks. |
| |
Keywords: | Combinatorial problems Feedback vertex set Shuffle exchange de Bruijn Kautz |
本文献已被 ScienceDirect 等数据库收录! |
|