Given a graph, the minimum feedback vertex set is a subset of vertices of minimum size whose removal induces an acyclic subgraph. The problem of finding the minimum feedback vertex set is NP-hard for general networks but interesting polynomial solutions have been found for particular graph classes. In this paper we find close upper and lower bounds to the size of the minimum feedback vertex in a k-dimensional hypercube.

Feedback Vertex Set in Hypercubes

FOCARDI, Riccardo;LUCCIO, Flaminia;
2000-01-01

Abstract

Given a graph, the minimum feedback vertex set is a subset of vertices of minimum size whose removal induces an acyclic subgraph. The problem of finding the minimum feedback vertex set is NP-hard for general networks but interesting polynomial solutions have been found for particular graph classes. In this paper we find close upper and lower bounds to the size of the minimum feedback vertex in a k-dimensional hypercube.
2000
76/1-2
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/16115
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 58
  • ???jsp.display-item.citation.isi??? 56
social impact