Elsevier

Theoretical Computer Science

Volume 383, Issue 1, 12 September 2007, Pages 86-101
Theoretical Computer Science

Feedback vertex sets in mesh-based networks

https://doi.org/10.1016/j.tcs.2007.03.051Get rights and content
Under an Elsevier user license
open archive

Abstract

In this paper, we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal cardinality subset of the vertices, whose removal makes a graph acyclic. The problem is NP-hard for general topologies, but optimal and near-optimal solutions have been provided for particular networks. In this paper, the problem is considered for undirected graphs with the following topologies: two- and higher-dimensional meshes of trees, trees of meshes, and pyramid networks. For the two-dimensional meshes of trees the results are optimal; for the higher-dimensional meshes of trees and the tree of meshes the results are asymptotically optimal. For the pyramid networks, there remains a small factor between the upper and the lower bounds.

Keywords

Combinatorial optimization
Feedback vertex set
Mesh of trees
Tree of meshes
Pyramid

Cited by (0)

A preliminary version of this paper appeared as [F.L. Luccio, J.F. Sibeyn, Tighter bounds on feedback vertex sets in mesh-based networks, in: Proc. 11th International Colloquium on Structural Information and Communication Complexity, in: LNCS, vol. 3104, Springer Verlag, 2004, pp. 209–220]. Work partially supported by Abstract Interpretation Design and Applications, AIDA, MIUR COFIN Project.

1

This work is dedicated to one of the authors, Jop Sibeyn, who very unfortunately has disappeared since March 15, 2005, probably victim of a fatal accident. It was a pleasure to work and collaborate with such an enthusiastic and nice person.

His colleague, coauthor and friend, Flaminia Luccio.