Publications [#331475] of John H. Reif

Conference articles PUBLISHED

1. Pan, V; Reif, J, Extension of the parallel nested dissection algorithm to path algebra problems, in Lecture Notes in Computer Science, Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, vol. 241 LNCS (January, 1986), pp. 470-487, Springer Berlin Heidelberg, ISBN 9783540171799 [pdf], [doi]
   (last updated on 2026/01/15)

   Abstract:
   This paper extends the author's parallel nested dissection algorithm of [PR] originally devised for solving sparse linear systems. We present a class of new applications of the nested dissection method, this time to path algebra computations, (in both cases of single source and all pair paths), where the path algebra problem is defined by a symmetric matrix A whose associated graph G with n vertices is planar. We substantially improve the known algorithms for path algebra problems of that general class: (Table presented.) (In case of parallel algorithms we assume that G is given with its O(√n)-separator family.) Further applications lead, in particular, to computing a maxflow and a mincut in an undirected planar network using O(log⁴n) parallel steps, n^1.5/log n processors or alternatively O(log³n) steps, n²/log n processors, versus the known bounds, O(log²n) and n⁴, of [JV].