Parallel nested dissection for path algebra computations

DOI10.1016/0167-6377(86)90074-XzbMath0632.90024OpenAlexW1974567149MaRDI QIDQ1095781

John H. Reif, Pan, Victor Y.

Publication date: 1986

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(86)90074-x

zbMATH Keywords

path problemscomplexity boundsmulticommodity flowplanar networknested decomposition parallel algorithmpost-optimizationsolution of linear systemsundirected planar graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Related Items

Efficient algorithms for solving systems of linear equations and path problems

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• How to multiply matrices faster
• An efficient parallel algorithm for planarity
• Efficient parallel linear programming
• Dioïds and semirings: Links to fuzzy sets and other applications
• On a routing problem
• An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
• A Separator Theorem for Planar Graphs
• Generalized Nested Dissection
• A Unified Approach to Path Problems
• Fast Algorithms for Solving Path Problems
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time