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.
2003
Proceedings in Informatics
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/27006
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact