Now showing items 1-2 of 2
Selection in monotone matrices and computing kth nearest neighbors
An m x n matrix A=(ai j),1,i,m and 1,j<n is called a totally motone matrix if for i1.i2.j1.j2satisfying1=i1.i2.m1=j1.j2.n ai1.ji1<ai1.j2=ai2j1<ai2.j2.We present an O ((m+n)nlogn time algorithm to select the kth smallest ...
AnO(n) Algorithm for Abelianp-Group Isomorphism and anO(n log n) Algorithm for Abelian Group Isomorphism
The isomorphism problem for groups is to determine whether two finite groups are isomorphic. The groups are assumed to be epresented by their multiplication tables. Tarjan has shown that this problem can bedone in time ...