An Almost Linear Time Algorithm for Generalized Matrix Searching
An Almost Linear Time Algorithm for Generalized Matrix Searching
复制标题
广义矩阵搜索的近线性时间算法
DOI：
--
复制
发表时间：
1990
影响因子：
0.8
通讯作者：
D. Kleitman
中科院分区：
文献类型：
--
作者：
M. Klawe;D. Kleitman
给出了求完全单调部分n元矩阵的行极大值和极小值的$O(Malpha(N)+n)$time算法。对于两个凸多边形顶点之间的距离和可见性等优化问题，得到了更快的算法。文中还给出了如何对算法进行修改以给出一类满足凸四边形不等式的动态规划问题的$O(nα(N))$算法。这为分子生物学、语音识别和地质学中出现的许多问题带来了更快的算法。
An $O( malpha ( n ) + n )$ time algorithm is given for finding row-maxima and minima in totally monotone partial $n imes n$ matrices. As a result, faster algorithms are obtained for some optimization problems concerning distance and visibility between vertices of two convex polygons. Also shown is how the algorithm can be modified to give an $O( n alpha ( n ) )$ algorithm for a class of dynamic programming problems satisfying convex quadrangle inequalities. This results in faster algorithms for a number of problems arising in molecular biology, speech recognition, and geology.