Extension of the parallel nested dissection algorithm to path algebra problems


Conference Paper

© 1986, Springer Verlag. All rights reserved. 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(log4n) parallel steps, n1.5/log n processors or alternatively O(log3n) steps, n2/log n processors, versus the known bounds, O(log2n) and n4, of [JV].

Full Text

Duke Authors

Cited Authors

  • Pan, V; Reif, J

Published Date

  • January 1, 1986

Published In

Volume / Issue

  • 241 LNCS /

Start / End Page

  • 470 - 487

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783540171799

Digital Object Identifier (DOI)

  • 10.1007/3-540-17179-7_29

Citation Source

  • Scopus