Show simple item record

dc.contributorKrishna M. Kavi Program Manageren_US
dc.contributor.authorXin He Principal Investigatoren_US
dc.datestart 06/15/1990en_US
dc.dateexpiration 05/31/1993en_US
dc.date.accessioned2014-04-02T18:16:49Z
dc.date.available2014-04-02T18:16:49Z
dc.date.issued2014-04-02
dc.identifier9011214en_US
dc.identifier.urihttp://hdl.handle.net/10477/22431
dc.descriptionGrant Amount: $ 35581en_US
dc.description.abstractThis project is concerned with the design of efficient parallel algorithms for solving various graph problems arising from disparate areas in Computer Science. These problems can be roughly divided into three categories: graph layout problems, some fundamental problems for planar graphs, and optimization problems for a class of special graphs including permutation graphs, comparability graphs, and cographs. Because of their broad applications in a variety of applied science disciplines, sequential algorithms for these problems have been extensively studied. But it appears difficult to solve them in parallel. Either no fast parallel algorithms for solving them are known; or parallel algorithms exist, but require a very large number of processors. The properties of these graphs and intrinsic structures of these problems will be investigated, and new parallel algorithms for solving them will be developed (or the efficiency of existing parallel algorithms will be improved). A main concern of this project is to identify common characteristics and to find algorithmic tools for the problems in each category. The results produced from this study will provide not only efficient parallel algorithms for individual problems, but also new understanding of these special graphs and new techniques for designing parallel algorithms.en_US
dc.titleParallel Algorithm for Special Graphsen_US
dc.typeNSF Granten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record