| Popis: |
The all-pairs-shortest-length (APSL) problem has been quite rigorously studied on various graphs. On general graphs, solutions are known for both the unweighted and weighted cases. Recently Seidel (1992) showed that the APSL problem on unweighted graphs can be solved in O(M(n)log n) time with O(n2) space. Here M(n) denotes the complexity of multiplying two matrices of small integers, which is currently O(n2.376). The APSP problem has been solved on the class of permutation graphs (a subclass of co-comparability graphs) with the complexity O(n + T) where T is the sum of the lengths of all the shortest paths (Mahesh, 1989). On the classes of interval and circular-arc graphs, an optimal solution to the APSL problem is available for the weighted case (Atallah et al; 1993). In this paper, we discuss the APSL problem on the class of strongly chordal graphs. There is no algorithm known for the APSL problem on this class of graphs. We present an O(n2) algorithm to compute the lengths of the shortest-paths that also enables us to retrieve the paths in optimal time. The solution is for unweighted strongly chordal graphs. |
