Given an undirected and vertex weighted graph G, the Weighted Feedback Vertex Problem (WFVP) consists in finding a subset F⊆V of vertices of minimum weight such that each cycle in G contains at least one vertex in F. The WFVP on general graphs 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 WFVP on it.

A linear time algorithm for the minimum Weighted Feedback Vertex Set on diamonds

PARLATO G
2005-01-01

Abstract

Given an undirected and vertex weighted graph G, the Weighted Feedback Vertex Problem (WFVP) consists in finding a subset F⊆V of vertices of minimum weight such that each cycle in G contains at least one vertex in F. The WFVP on general graphs 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 WFVP on it.
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.

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