Title: A linear-time algorithm for the weighted feedback vertex problem on interval graphs
Abstract: We present a linear-time algorithm for finding a minimum weighted feedback vertex set on interval graphs using the dynamic programming technique. Since the weighted feedback vertex problem, the weighted C3,1 problem, the maximum weighted 2-colorable subgraph problem and the maximum weighted 2-independent set problem are equivalent on chordal graphs, we can solve the latter three problems in linear-time on interval graphs, too.
Publication Year: 1997
Publication Date: 1997-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 55
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot