Given a vertex weighted graph G, a minimum Weighted Feedback Vertex Set (MWFVS) is a subset F ⊆ V of vertices of minimum weight such that each cycle in G contains at least one vertex in F. The MWFVS on general graph is known to be NP-hard. In this paper we introduce a new class of graphs, namely the diamond graphs, and give a linear time algorithm to solve MWFVS on it. We will discuss, moreover, how this result could be used to effectively improve the approximated solution of any known heuristic to solve MWFVS on a general graph.
A Linear Time Algorithm for the Minimum Weighted Feedback Vertex Set on Diamonds
PARLATO G
2004-01-01
Abstract
Given a vertex weighted graph G, a minimum Weighted Feedback Vertex Set (MWFVS) is a subset F ⊆ V of vertices of minimum weight such that each cycle in G contains at least one vertex in F. The MWFVS on general graph is known to be NP-hard. In this paper we introduce a new class of graphs, namely the diamond graphs, and give a linear time algorithm to solve MWFVS on it. We will discuss, moreover, how this result could be used to effectively improve the approximated solution of any known heuristic to solve MWFVS on a general graph.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
