9402334 Sanchis This project involves investigation into various problems having to do with efficient construction and generation of structures. In part it will include continued research in the area of generation of test cases for NP-hard problems. As part of this effort, further investigation will be done on the construction of test cases for certain NP-hard graph problems, including the maximum clique problem and the dominating set problem. This work will include both improvement of previous test case generating procedures, and consideration of new approaches. In particular, the relationship between the hardness (both theoretical and experimental) of constructed test cases, and various instance parameters (such as the edge density of the graph) will be further investigated. Some related extremal graph theory problems arising from the construction procedures will also be studied. The project also involves more theoretical aspects of the generation and construction problems. This area is concerned with the feasibility and/or complexity of the construction and generation problem for various types of languages and structures. Some unanswered questions in this area will be further investigated. ***
