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