In this paper, we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal cardinality subset of the vertices, whose removal makes a graph acyclic. The problem is NP-hard for general topologies, but optimal and near-optimal solutions have been provided for particular networks. In this paper, the problem is considered for undirected graphs with the following topologies: two- and higher-dimensional meshes of trees, trees of meshes, and pyramid networks. For the two-dimensional meshes of trees the results are optimal; for the higher-dimensional meshes of trees and the tree of meshes the results are asymptotically optimal. For the pyramid networks, there remains a small factor between the upper and the lower bounds.
Feedback Vertex Sets in Mesh-based Networks.
LUCCIO, Flaminia;
2007-01-01
Abstract
In this paper, we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal cardinality subset of the vertices, whose removal makes a graph acyclic. The problem is NP-hard for general topologies, but optimal and near-optimal solutions have been provided for particular networks. In this paper, the problem is considered for undirected graphs with the following topologies: two- and higher-dimensional meshes of trees, trees of meshes, and pyramid networks. For the two-dimensional meshes of trees the results are optimal; for the higher-dimensional meshes of trees and the tree of meshes the results are asymptotically optimal. For the pyramid networks, there remains a small factor between the upper and the lower bounds.File | Dimensione | Formato | |
---|---|---|---|
tcs07.pdf
non disponibili
Tipologia:
Documento in Post-print
Licenza:
Accesso chiuso-personale
Dimensione
1.14 MB
Formato
Adobe PDF
|
1.14 MB | Adobe PDF | Visualizza/Apri |
I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.