Minimum Feedback Vertex Set in Pyramid and Mesh of Trees Networks.
Flaminia L. Luccio · ARCA (Università Ca' Foscari Venezia) · 2003
In this paper we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal subset of vertices that have to be removed from a graph, to induce an acyclic subgraph. The problem in NP-hard for general topologies, but many different polynomial time algorithms have been provided for particular networks. In this paper we present close lower and upper bounds to the problem in two different topologies, namely pyramid networks and rectangular mesh of trees networks.