Li Sheng

Associate Professor
Department of Mathematics
Drexel University.
3141 Chestnut Street
Philadelphia, PA 19104

Office: Korman 6 - 274
Voice: (215) 895-6613
FAX: (215) 895-1582

Office hours (Winter13): MF 11:00 AM -- 12:00 AM, W: 8:00 AM -- 9:00 AM or by appointment 









  1998, Ph.D in Operations Research, RUTCOR, Rutgers University, New Brunswick, NJ
  1996, M.S in Statistics, Rutgers University, New Brunswick, NJ
  1991, M.S in Operations Research, Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing, China
  1988, B.S in Mathematics, National University of Defense Technology, Changsha, China


Courses Currently Taught

        Mathematics for Nursing Professionals (Math108): Winter13


Research Interest:

                  My research interests are primarily in discrete mathematics, with an emphasis on graph theory, and with an interest in applications, especially to the biological, communication, information, social and transportation sciences.

                  For the applications of graph theory to biological science, I have  introduced the model called tagged probe interval graphs, a refinement of the interval graph model that       can be used in DNA physical mapping for reconstructing the relative position of the short DNA      segments along their original long DNA string using the overlapping information between the short DNA segment. I have also  introduced the notions of phylogeny graph and phylogeny numbers, which can serve as a model for reconstructing phylogenetic (evolutionary) tree of different biological species based on similarities among the species.

                  I have conducted research on the role assignment model to problems of social networks. The general goal of social network analysis is to replace a large network with a smaller one which still preserve the relational structure of the original network. Role assignment model provide one way to do so by aggregating similar data into one group, it is based on the idea that if social role is defined properly, then individual with the same social role will related in the same way to individuals playing counterpart roles. It is a variant of the notion of graph coloring, and it serve as a model for cluster analysis.

                 Recently, I have involved in the research of Routing in multicomputer systems, a collection of processors (also called nodes) work together to solve large application problems. These nodes communicate and coordinate their efforts by sending and receiving messages through the underlying communication network. Routing is the process of transmitting message from one node to another. In order to ensure that every message is eventually delivered, the routing algorithm must be free of deadlock. Routing time of messages is another key factors critical to the performance of multicomputers. We developed routing algorithm using prefix-based routing scheme, we shown our routing algorithm is deadlock free and cost effective for preprocessing. We also provide a compact proof for a tighter lower bound on the number of Channels (also called links) required for deadlock-free routing. The result can be used for communication network designers as a general guide to rule out certain topologies that do not admit deadlock-free routing.

               I have also recently collaborated in the research on applied the concept of quandratic residual of number theory to solve some extremal sequences problems in graph theory.

Selected Publications Last modified: Jan 1, 2002