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.
Minimum Feedback Vertex Set in Pyramid and Mesh of Trees Networks
LUCCIO, Flaminia
2003-01-01
Abstract
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.