The principal theme of this research is the application of group-theoretic techniques to a wide variety of search problems. The ultimate objective is to combine algebraic techniques with standard search methods to solve "hard problems" which are currently solvable by neither method alone. This requires the interaction of three major research efforts: the study of efficient algorithms for performing fundamental group computations; the development of an experimental system for testing algorithmic ideas on both sequential and parallel machines; and the exploration of methods for representing search problems in an algebraic setting and tools for solving them. The algorithms to be studied play a fundamental role in the development of general algorithms for computing with groups as well as for application of group theory to real world problems. Applications are diverse and range from isomorphism testing of combinatorial objects to the transportation problems in operations research. Both algorithms and applications will be implemented in both a traditional sequential environment engineered to support experimentation with a variety of data structures and techniques, and, where suitable, on a massively parallel SIMD machine.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Application #
9204469
Program Officer
S. Kamal Abdali
Project Start
Project End
Budget Start
1992-08-01
Budget End
1996-01-31
Support Year
Fiscal Year
1992
Total Cost
$332,970
Indirect Cost
Name
Northeastern University
Department
Type
DUNS #
City
Boston
State
MA
Country
United States
Zip Code
02115