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

Posted on November 30, 2017 by | Leave a comment

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
This entry was posted in Handouts. Bookmark the permalink.

Leave a Reply

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