Algorithm Engineering Group

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.

Combinatorial generation is to generate combinatorial objects systematically one by one with a minimum amount of effort. Combinatorial objects such as permutations are as old as human history. In ancient times, diplomats were worrying about how to sit dignitaries around the dinner table in a different way each time. The following is a systematic way to generate well formed parenthesis strings by swapping a pair of parenthesis each time.

• Combinatorial Generation by Fusing Loopless Algorithms, CATS06, Hobart.

The maximum sub array problem is to find a rectangular position whose sum is maximum in a given two dimensional array. Two typical areas of application are graphics and data mining. In graphics, the maximum sub array corresponds to the brightest spot in the given graphic image. In data mining, the maximum sub array corresponds to the most promising customer range found in the given relational database.

Subarray Problems

• Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, CATS '02.
• The Reverse Problem of Range Query, CATS '03.