On the longest increasing subsequence of a circular list

The longest increasing circular subsequence (LICS) of a list is considered. A Monte Carlo algorithm to compute it is given which has worst case execution time O(n3/2logn) and storage requirement O(n). It is proved that the expected length μ(n) of the LICS satisfies . Numerical experiments with the algorithm suggest that .     

Improved generalized Atkin algorithm for computing square roots in finite fields

Recently, S. Müller developed a generalized Atkin algorithm for computing square roots, which requires two exponentiations in finite fields GF(q) when . In this paper, we present a simple improvement to it and the improved algorithm requires only one exponentiation for half of squares in finite fields GF(q) when . Furthermore, in finite fields GF(pm), where and m is odd, we reduce the complexity of the algorithm from O(m³log³p) to O(m²log²p(logm+logp)) using the Frobenius map and normal basis representation.     

Bottleneck flows in unit capacity networks

The bottleneck network flow problem (BNFP) is a generalization of several well-studied bottleneck problems such as the bottleneck transportation problem (BTP), bottleneck assignment problem (BAP), bottleneck path problem (BPP), and so on. The BNFP can easily be solved as a sequence of O(logn) maximum flow problems on almost unit capacity networks. We observe that this algorithm runs in O(min{m3/2,n2/3m}logn) time by showing that the maximum flow problem on an almost unit capacity graph can be solved in O(min{m3/2,n2/3m}) time. We then propose a faster algorithm to solve the unit capacity BNFP in time, an improvement by a factor of at least . For dense graphs, the improvement is by a factor of . On unit capacity simple graphs, we show that BNFP can be solved in time, an improvement by a factor of . As a consequence we have an algorithm for the BTP with unit arc capacities.