Research in the design of efficient algorithms. It centers on finding algorithms that improve the asymptotic efficiency of solutions to classical problems, such as sorting, shortest path, all pairs shortest paths, shortest paths on polyhedron, connected components, minimum spanning tree and variations of these that limits input variables to being integers.
Recent and Current Research
All-pairs Shortest Paths
It has been known that all-pairs shortest paths can be computed in subcubic time when edge weights are small integers. When edge weights are real the complexity has been improving with the work of many researchers, but it has always been near cubic time. This project is aimed at studying whether truly subcubic time can be achieved for all-pairs shortest paths.
The current fastest matrix multiplication algorithm of Coppersmith and Winograd has kept record for almost 30 years and has become the bottleneck of many other algorithms or applications. This project is to study whether breakthrough can be obtained over the current record of n2.376 time.
There are many aspects of maximum flow. Currently we have a result that achieved certain degree of success over previously best results. The algorithm we have now faces some obstacles to generalize its results to all extent. Our intention is to generalize the algorithm so that it applies to all ranges of parameters.