Masters Theses

Date of Award

5-2004

Degree Type

Thesis

Degree Name

Master of Science

Major

Electrical Engineering

Major Professor

Dr. Gregory D. Peterson

Committee Members

Dr. Donald W. Bouldin, Dr. Michael A. Langston, Dr. Chandra Tan, Dr. Philip Locasio

Abstract

Active research has been done in the past two decades in the field of computational intractability. This thesis explores parallel implementations on a RC (reconfigurable computing) platform for FPT (fixed-parameter tractable) algorithms.

Reconfigurable hardware implementations of algorithms for solving NP-Complete problems have been of great interest for research in the past few years. However, most of the research that has been done target exact algorithms for solving problems of this nature. Although such implementations have generated good results, it should be kept in mind that the input sizes were small. Moreover, most of these implementations are instance-specific in nature making it mandatory to generate a different circuit for every new problem instance.

In this work, we present an efficient and scalable algorithm that breaks out of the conventional instance-specific approach towards a more general parameterized approach to solve such problems. We present approaches based on the theory of fixed-parameter tractability. The prototype problem used as a case study here is the classic vertex cover problem. The hardware implementation has demonstrated speedups of the order of 100x over the software version of the vertex cover problem.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS