Parallel nested dissection for path algebra computations


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Pan, V; Reif, J

Published Date

  • January 1, 1986

Published In

Volume / Issue

  • 5 / 4

Start / End Page

  • 177 - 184

International Standard Serial Number (ISSN)

  • 0167-6377

Digital Object Identifier (DOI)

  • 10.1016/0167-6377(86)90074-X

Citation Source

  • Scopus