Date: Monday, 25-Nov-96 22:58:33 GMT
Server: NCSA/1.3
MIME-version: 1.0
Content-type: text/html
Dr. Sprague's home page
Alan P. Sprague
Associate Professor
Schedule
Research Interests
Parallel Graph Algorithm and Computational Geometry
The parallel graph algorithm research centers on algorithms for special classes
of graphs, such as chordal graphs. Similar techniques and concepts lead to
algorithms for certain computational geometry problems, such as a parallel
algorithm to construct the constraint graph, used in compaction of VLSI
circuits.
Parallel Tree Search Algorithms
Tree searching methods are used in artificial intelligence (AI) and
optimization, plus various other areas. Branch and bound is one tree search
method. This research centers on how to partition the branch-and-bound task
for a multiprocessor, and how to partition the data structures used, both
for shared memory and distributed memory systems. Other research addresses
different search strategies, including alpha-beta minimax, best-first, and
breadth-first, to name a few. The issues being addressed include
distributing the coach among either shared memory multiprocessors or
distributed memory multiprocessors, and interprocessor communication to
maximize search efficiency by letting each processor show search information.
Education
Ohio State University
Selected Publications