1243 - Polynomial-time Reductions

All about problems in Volume 12. 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
Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 1243 - Polynomial-time Reductions

Post by Repon kumar Roy »

Hints :
1. Convert into DAG by calculating SCC
2. In the dag, Build a new graph using all possible edges
3. Now remove the redundant edges
The third step is tricky. Takes O(m*n)
Top
Post Reply

Return to “Volume 12 (1200-1299)”