Computer Science & Engineering
University of Nevada, Reno, USA
By Prof. Fred Harris, Jr., Computer Science & Engineering, University of Nevada, Reno, USA.
Given a set of cities, construct a connected network which has minimum length. The problem is simple enough, but the catch is that you are allowed to add junctions in your network. Therefore the problem becomes how many extra junctions should be added, and where should they be placed so as to minimize the overall network length. This intriguing optimization problem is known as the Steiner Minimal Tree Problem (SMT), where the junctions that are added to the network are called Steiner Points.
We will begin with a brief overview of the problem, present an approximation algorithm which performs very well, then review the computational algorithms implemented for this problem. We will then shift to a parallel algorithm for the generation of what Pawel Winter termed T list and its implementation. This generation of T list is followed by the extraction of the proper answer. When Winter developed his algorithm, the time for extraction dominated the overall computation time. After Cockayne and Hewgill’s work, the time to generate T list dominated the overall computation time. The parallel algorithms presented here were implemented, and the results show that the time to generate T list has now been cut by an order of magnitude. So now the extraction time once again dominates the overall computation time. Interesting application to grids as well as a grammar with rewrite rules are presented for characterizations of SMT’s for 2xm, 3 x m, 4 x m, 5 x m, 6 x m, and 7 x m grids.
Biography
Frederick C. Harris Jr. received his BS and MS degrees in Mathematics and Educational Administration from Bob Jones University, Greenville, SC, USA in 1986 and 1988 respectively. He then went on and received his MS and Ph.D. degrees in Computer Science from Clemson University, Clemson, SC, USA in 1991 and 1994 respectively.
He is currently a Professor in the Department of Computer Science and Engineering and the Director of the High Performance Computation and Visualization Lab at the University of Nevada, Reno, USA. He is also the Nevada State EPSCoR Director and the Project Director for Nevada NSF EPSCoR. He has published more than 275 peer-reviewed journal and conference papers along with several book chapters. He has had 14 PhD students and 78 MS Thesis students finish under his supervision. His research interests are in parallel computation, simulation, computer graphics, and virtual reality. He is also a Senior Member of the ACM, and a Senior Member of the International Society for Computers and their Applications (ISCA).