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

• Sub-cubic Algorithms for the All Pairs Shortest Path Problems, WG '95.
• Shortest Path Algorithms for Nearly Acyclic Directed Graphs, WG '96.
• Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, CATS '02.
• Improved Shortest Path Algorithms for Nearly Acyclic Graphs, to appear in Theoretical Computer Science.

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, Cocoon '99.
• Theory of 2-3 Heaps, To appear in Discrete Applied Math.
• Theory of Trinomial Heaps, Cocoon '00.