A linear time algorithm for the minimum weighted feedback vertex set on diamonds

DOI10.1016/j.ipl.2004.12.008zbMath1182.68145OpenAlexW2062338515MaRDI QIDQ1041719

Francesco Carrabs, Gennaro Parlato, Monica Gentili, Raffaele Cerulli

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://eprints.soton.ac.uk/272467/1/sdarticle%25281%2529.pdf

zbMATH Keywords

dynamic programminggraph algorithmsdiamondweighted feedback vertex set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

MIP formulations for induced graph optimization problems: a tutorial ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review ⋮ Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem

Cites Work

• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• On the feedback vertex set problem in permutation graphs
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: A linear time algorithm for the minimum weighted feedback vertex set on diamonds