Maximum Independent Set on graph with one simple cycle

Revision en1, by winaichan263, 2016-04-23 15:34:13

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English 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 English winaichan263 2016-04-23 15:34:13 517 Initial revision (saved to drafts)