Grant: Discovery Grants Program - Individual

My research is concerned with designing efficient parallel algorithms. Specifically, I will concentrate on (1) parallel algorithms and data structures, and (2) combinatorial/graph theoretical properties of interconnection networks. Both fundamental and application algorithms will be considered. Fundamental algorithms are algorithms that many applications use frequently. They include routing algorithms, broadcasting (and its variations) and various other data communication algorithms. As for applications, various problems will be considered, e.g., the traditional combinatorial ones such as sorting and searching, graph algorithms and algorithms in computational geometry, as well as algorithms for sequence comparison/analysis in bioinformatics. The underlining topology for a machine is important to the design of system software such as message passing interface, application algorithms, communication primitives, and thus, the overall performance of the system. We will investigate the topological/combinatorial properties of some of the networks such as Cayley graphs so that we can take advantage of these properties in designing efficient routing/communication algorithms and parallel application algorithms. Another interesting and important aspect of interconnection networks is their combinatorial properties such as the Whitney numbers of the second kind for the poset associated with the graphs (also known as the surface area). These numbers have applications in computing various bounds for data communications, average distances, and transmissions of graphs. In addition, such a study may have applications in genome rearrangement since the vertex set of a Cayley graph is a set of permutations and the vertices may represent genomes and mutations from one genome to another is equivalent to routing on certain Cayley graphs.