Cascade Algorithm Revisited

Type of content
Theses / Dissertations
Publisher's DOI/URI
Thesis discipline
Degree name
Other
Publisher
University of Canterbury
Journal Title
Journal ISSN
Volume Title
Language
English
Date
2014
Authors
Takaoka, Tadao
Umehara, Kiyomi
Abstract

We revisit the cascade algorithm for the all pairs shortest path (APSP) problem. The operation on the distace data is limited to the triple operation of min{a, b + c}. The best known complexity on this model is n 3 by Floyd’s algorithm. The cascade algorithm takes 2n 3 opearations. We first improve this bound to n 3 , that is, on a par with Floyd’s algorithm. Then we implement the improved version on a mesh computer and achieve 3n − 2 communication steps.

Description
Citation
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Rights
All Right Reserved