Parallel nested dissection for path algebra computations (Q1095781)

The authors apply previous results for the solution of linear systems by their nested decomposition parallel algorithm to the class of path problems on undirected planar graphs, or more generally, to graphs that have a small, easily computable, separator family. Problems of this class are: existence problems, (of paths having k (or at most k) edges between i and j, transitive closure, testing for strong connectivity or circuits), path enumeration, optimization, counting and optimization or post-optimization (k-th path, \(\eta\)-optimal path). Using the linear algebra algorithm yields complexity bounds lower than the previously published values, both in a serial and parallel environment, for the single-source as well as the all-pairs version of the problem. The reductions obtained are: 1. Time complexity of the sequential algorithm: Single source: \(O(n^{1.5})\) instead of \(O(n^ 2)\) previously. All pairs: \(O(n^ 2)\) instead of \(O(n^ 3).\) 2. Time/no processor for the parallel algorithm: Single source: \(O(\log^ 3n)\) time and \(n^{1.5}/\log n\) no processor instead of \(O(\log^ 2n)\) and \(n^ 3\) previously. All pairs: \(O(\log^ 3n)\) time and \(n^ 2/\log n\) no processor instead of \(O(\log^ 2n)\) and \(n^ 3\) previously.