Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems

DOI10.1007/3-540-58338-6_93zbMath1493.68272OpenAlexW4249165371MaRDI QIDQ5096905

Dimitris J. Kavvadias, Christos D. Zaroliagis, Grammati E. Pantziou, Paul G. Spirakis

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11858/00-001M-0000-0014-B521-0

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Matrix multiplication via arithmetic progressions
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• Designing networks with compact routing tables
• Parallel computational geometry
• Efficient parallel algorithms for shortest paths in planar digraphs
• Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
• The graph genus problem is NP-complete
• Priority Search Trees
• An O(logn) parallel connectivity algorithm
• Planar graph decomposition and all pairs shortest paths
• Fibonacci heaps and their uses in improved network optimization algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems