| dc.description.abstract | The k-path problem is to find a simple path of length k. This
problem is NP-complete and has applications in bioinformatics for
detecting signaling pathways in protein interaction networks and for biological subnetwork matching. There are algorithms implemented to
solve the problem for k up to 13. The fastest implementation has
running time O^*(4.32^k), which is slower than the best known algorithm of running time O^*(4^k). To implement the best known algorithm for the k-path problem, we need to construct (n,k)-universal set.
In this thesis, we study the practical algorithms for constructing the (n,k)-universal set problem. We propose six algorithm variants to
handle the increasing computational time and memory space needed for
k=3, 4, ..., 8. We propose two major empirical techniques that cut
the time and space tremendously, yet generate good results. For the case k=7, the size of the universal set found by our algorithm is 1576, and is 4611 for the case k=8.
We implement the proposed algorithms with the OpenMP parallel interface and construct universal sets for k=3, 4, ..., 8. Our experiments show that our algorithms for the (n,k)-universal set problem exhibit very good parallelism and hence shed light on its MPI implementation.
Ours is the first implementation effort for the (n,k)-universal set
problem. We share the effort by proposing an extensible universal set construction and retrieval system. This system integrates universal set construction algorithms and the universal sets constructed. The sets are
stored in a centralized database and an interface is provided to access the database easily.
The (n,k)-universal set have been applied to many other NP-complete
problems such as the set splitting problems and the matching
and packing problems. The small (n,k)-universal set constructed
by us will reduce significantly the time to solve those problems. | en |
