This web site is no longer maintained and the content may be outdated.
Please visit www.cmpe.boun.edu.tr for up-to-date information.
 
CmpE RSS
No upcoming events...

Home / Graduate / PhD Theses Completed
 
 
 
 
  Nahit Emanet, 2004    

Thesis Title

Sequential and parallel algorithms for the rectilinear steiner tree problem


Abstract

The rectilinear Steiner tree problem is an NP-complete problem with many important applications in networks and very large scale integration (VLSI) design. This thesis examines the rectilinear Steiner tree problem and proposes sequential and parallel branch and cut algorithms to solve it.In this thesis, we present two new LP constraints, cutsec constraints and strong incompatibility constraints that allow us to greatly reduce the time to solve the problem. We also present a message passing parallel algorithm to solve large problem instances in a heterogenous computing environment. Both sequential and parallel algorithms are united in a program that is written in C++ programming language by using object-oriented methodology. We look at the experimental results of the presented algorithms by performing benchmark tests on TSP and ES1000FST instances from the SteinLib library. Average running time of the algorithms to solve the rectilinear Steiner minimal tree (RSMT) problem to optimality are better than that of other competing algorithms.We can also say that our program can be a base for other new developing algorithms due to its interface that facilitates improvements and modifcations.
 
 
Boğaziçi University Department of Computer Engineering
Address: 34342 Bebek, Istanbul, TURKEY
Phone: +90 212 359 4523-24 Fax: +90 212 287 2461
general information: infocmpe.boun.edu.tr   webmaster: webmastercmpe.boun.edu.tr