Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.ipl.2004.12.008 | Inf. Process. Lett. |
Keywords | Field | DocType |
general graph,linear time algorithm,new class,minimum weight,minimum weighted feedback vertex,diamond graph,subset f,weighted feedback vertex problem,vertex weighted graph,dynamic programming,diamond,feedback vertex set | Discrete mathematics,Combinatorics,Indifference graph,Vertex (graph theory),Chordal graph,Neighbourhood (graph theory),Algorithm,Cycle graph,Vertex cover,Feedback vertex set,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
94 | 1 | 0020-0190 |
Citations | PageRank | References |
3 | 0.40 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| F. Carrabs | 1 | 6 | 1.14 |
| R. Cerulli | 2 | 252 | 23.85 |
| M. Gentili | 3 | 32 | 3.35 |
| G. Parlato | 4 | 6 | 1.49 |