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.
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.
