10984 - Double NP-hard

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ »

I got ..P.E (the 50-th PE) at last
Thanks Hadi and kp for your explanations
Thanks Adbenego, nice problems :)
Top
DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:
Contact DD

Re: 10984 - Double NP-hard

Post by DD »

It is really a nice problem. Since minimum vertex cover and maximum independent set are dual, with clever combinations and modifications this problem become polynominal time solvable. Thanks problem setter :D
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.
Top
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Contact Abednego

Re: 10984 - Double NP-hard

Post by Abednego »

You are welcome. I'm glad you liked it.
If only I had as much free time as I did in college...
Top
Post Reply

Return to “Volume 109 (10900-10999)”