Interval Graph K - Links Some Of The Most Short Circuit Problem Research

The problem that K-link shortest path on interval graphs is a hard kind problem of shortest path problem on interval graphs. We focus on K-link shortest path on n intervals and study the properties about interval graphs and the shortest path problems on interval graphs. Based on the intuition of dynamic programming and greedy algorithms, we present the first on-line algorithm for K-link shortest path on interval graphs and several other algorithms which also can solve that problem. The theoretical result shows one of the algorithms which combined with the path compression technique in data structure design can solve K-link shortest path problem on proper interval graph in O(nK) time, which is O(K) constant time complexity for each interval by amortized analysis; the time complexity of this algorithms is O(nK+nlgn) for the general interval graph, same as the best off-line algorithm for this problem as far as we know.