Algorithms for finding the maximum-density path and maximum subarray problems
Date Issued
2004
Date
2004
Author(s)
Lin, Rung-Ren
DOI
en-US
Abstract
We propose some algorithms to solve two problems in this thesis. The first problem is to find a length-constrained maximum-density path in a tree. Given a tree with n edges, we present two efficient algorithm for finding a maximum-density path of length at least L in O(nL) time. One of them is further modified to solve full m-ary trees in O(n) time. The other problem is to find the maximum subarray in a two-dimensional array. Given an m×n array of numbers, we develop two heuristic algorithms for computing the maximum subarray in O(nm + km^2), where k is a given parameter. Preliminary experiments show that these approaches are very promising for locating the maximum subarray in a given two-dimensional array.
Subjects
路徑
樹
子陣列
最大密度
path
tree
subarray
maximum-density
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-93-R91922054-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):b15f27b8b506b18f7db1d71e3cb8d5f7