Now showing items 1-5 of 5
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 ...
Optimal, output-sensitive algorithms for constructing planar hulls in parallel
In this paper we focus on the problem of designing very fast parallel algorithms for the planar convex hull problem that achieve the optimal O(n log H) work-bound for input size n and output size H. Our algorithms are ...
Fair adaptive bandwidth allocation: a rate control based active queue management discipline
Active queue management disciplines such as RED and its extensions have been widely studied as mechanisms for providing congestion avoidance, differentiated services and fairness between different traffic classes. With the ...
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
This paper presents improved algorithms for the following problem: given an unweighted directed graph G(V,E) and a sequence of on-line shortest-path/reachability queries interspersed with edge-deletions, develop a ...
Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima
In this paper we focus on the problem of designing very fast parallel algorithms for the convex hull and the vector maxima problems in three dimensions that are output-size sensitive. Our algorithms achieve O(loglog2 n log ...