Maximum Independent Set on graph with one simple cycle

Правка en2, от winaichan263, 2016-04-24 12:14:45

Hi. I've just started working on some DP + graph problems recently, but I've gotten stuck on one. It gives you a graph with exactly one simple cycle with no other vertices (all n vertices are on the cycle) and ask you to find the total cost of the maximum independent set of the graph. I know that it is a modification of maximum independent set on trees, but I don't know how to deal with the cycle. The farthest I've gotten is adding the first node as node n+1 and the dp recurrence. Can someone help me?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский winaichan263 2016-04-24 12:14:45 43 Tiny change: ' node n+1 ' -> ' node n+1 and the dp recurrence. Can someone help me?' (published)
en1 Английский winaichan263 2016-04-23 15:34:13 517 Initial revision (saved to drafts)