Shortest Paths
Faster algorithms for shortest paths have been designed, which incorporate structures of the given graphs into complexity analysis. The structural properties are based on the acyclicity of the given graph. More structural properties will be investigated in this project.
All pairs shortest path algorithms
- Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, CATS '02.
- Improved Shortest Path Algorithms for Nearly Acyclic Graphs, Theoretical Computer Science 293, 535-556, 2003.
- Solving SHortest Paths Efficiently on Nearly Acyclic Directed Graphs, Theoretical Computer Science, 2006.
- A Faster Algorithm for the All-Pairs Shortest Problem and its Application, COCOON 2004, LNCS 3106.
- An O(n^3loglogn/logn) time algorithm for the all-pairs shortest path problem, Information Processing Letters 96, 155-161, 2005.
- Improved Shortest Path Algorithms For Nearly Acyclic Directed Graphs. PDF file.
- Improved Shortest Path Algorithms For Nearly Acyclic Directed Graphs. Power Point.
- Efficient Algorithms for the 2-Center Problem, ICCSA 2010, Fukuoka, JAPAN, LNCS 6017, pp 519-532, 2010.
- Matrix Multiplication and All Pairs Shortest Paths In encyclopedia
- An O(n^3loglogn/log^2 n) Time Algorithm for All Pairs Shortest Paths In SWAT 2012
Data Structures
New data structures, called 2-3 heaps and trinomial heaps, have been designed in this project. Experiments show that these are more efficient than existing ones, such as Fibonacci heaps and relaxed heaps. In this project, there will be more discoveries in the area of dictionaries.
Data Structures algorithms
- Theory of 2-3 Heaps, Discrete Applied Math 126, 115-128, 2003.
- Theory of Trinomial Heaps, Cocoon '00.
