Steiner Tree Extraction

This project explores parallel algorithms for computing the final stage of Fred Harris's algorithm for Steiner Tree Extraction. The overall project was led by Roy Pargas.

I remembering finding it interesting that the problem is NP-complete, but that Pargas and gang were not going to give up! Instead, they worked on techniques to either find optimal solutions for larger problems, or approximate answers for problems even larger. It was neat to take part in it, and I learned an awful lot.

More details are in these papers:

• Spoon, Steven A. "A Parallel Branch-and-Bound Algorithm for Finding Steiner Minimal Trees". (student report).
• Pargas, Roy P., Jennifer Ludwick, and Steven A. Spoon. "Hybrid Search Algorithms". ACM Symposium on Applied Computing (SAC) 1997.