## Extension of the parallel nested dissection algorithm to path algebra problems

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].

### Duke Scholars

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Start / End Page

## Related Subject Headings

- Artificial Intelligence & Image Processing
- 46 Information and computing sciences

### Citation

*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*(Vol. 241 LNCS, pp. 470–487). https://doi.org/10.1007/3-540-17179-7_29

*Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, 241 LNCS:470–87, 1986. https://doi.org/10.1007/3-540-17179-7_29.

*Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, vol. 241 LNCS, 1986, pp. 470–87.

*Scopus*, doi:10.1007/3-540-17179-7_29.

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Start / End Page

## Related Subject Headings

- Artificial Intelligence & Image Processing
- 46 Information and computing sciences