Minimum feedback vertex sets in shuffle-based interconnection networks

✍ Scribed by Rastislav Královič; Peter Ružička

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 120 KB
• Volume: 86
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(02)00504-5

✦ Synopsis

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.