Sample Solutions to Pipe-Laying/NP-completeness for the Steiner Tree Problem

Here are sample solutions to the three parts of the Steiner Tree Problem worksheets:

  1. part 1 on understanding the problem and showing it is in NP
  2. part 2 on developing a reduction showing the problem is NP-hard
  3. part 3 on proving the reduction correct

Leave a Reply

Your email address will not be published. Required fields are marked *