Publications [#237106] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Pan, V; Reif, J, Parallel nested dissection for path algebra computations, Operations Research Letters, vol. 5 no. 4 (January, 1986), pp. 177-184, Elsevier BV, ISSN 0167-6377 [doi]
   (last updated on 2026/01/15)

   Abstract:
   This paper extends the authors' parallel nested dissection algorithm of [13] 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; this has further applications to maximum flow and minimum cut problems in an undirected planar network and to the feasibility testing of a multicommodity flow in a planar network. © 1986.