Back to results

Monterey, CA; Naval Postgraduate School

Efficient grid based techniques for solving the weighted region least cost path problem on multicomputers

Abstract

dc:description.abstract

This thesis explores the possibilities of developing fast grid parallel algorithms to solve the Weighted Region Least Cost Path problem. Two complimentary steps have been undertaken. First, an efficient sequential algorithm to solve the above problem was developed. the algorithm is a modification of a Gauss-Seidel-like algorithm for obtaining the minimum costs. The most salient feature of the algorithm is the reduction of the number of nodes and edges in cheaper regions of the grid. the reported experimental results ascertain the superiority of this algorithm with regard to computer running time at a modest reduction in the accuracy of the obtained solution. Parallel implementations of grid-based algorithms were studies. A simple grid-based variant was implemented on a network of Transputers. The overall approach is employed could be used to develop a parallel version of the above sequential algorithm on a Transputer network, combining both advantages of efficiency and parallelization.

Degree

thesis:*
Name thesis:degree_name
M.S. in Engineering Science
Level thesis:degree_level
Masters
Discipline thesis:degree_discipline
Engineering Science
Department dc:contributor.department
Department of Computer Science
Grantor dc:publisher
Monterey, CA; Naval Postgraduate School
Year dc:date.issued
1992

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ekin, Cengiz
Advisor dc:contributor.advisor
  • Zaky, Amr
Committee member dc:contributor.committeemember
  • Kwak, Sehung

Rights

dc:rights
Statement dc:rights
  • Copyright is reserved by the copyright owner.
  • Approved for public release; distribution is unlimited.

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10945/23654

Chain of custody

source
Harvested from
Naval Postgraduate School
Base URL
calhoun.nps.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ekin, Cengiz. Efficient grid based techniques for solving the weighted region least cost path problem on multicomputers. Masters thesis, Monterey, CA; Naval Postgraduate School, 1992. https://hdl.handle.net/10945/23654