Given a set P of n points and an integer k, we wish to place k facilities on points in P so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem, and the set of such k points is called a k-dispersion of P. Note that the 2-dispersion problem corresponds to the computation of the diameter of P. Thus, the k-dispersion problem is a natural generalization of the diameter problem. In this paper, we consider the case of k=3, which is the 3-dispersion problem, when P is in convex position. We present an O(n2)-time algorithm to compute a 3-dispersion of P.

A 3.3-V 512-k 18-b 2-bank synchronous DRAM (SDRAM) has been developed using a novel 3-stage-pipelined architecture. The address-access path which is usually designed by analog means is digitized, separated into three stages by latch circuits at the column switch and data-out buffer. Since this architecture requires no additional read/write bus and data amp, it minimizes an increase in die size. Using the standardized GTL interface, a 250-Mbyte/s synchronous DRAM with die size of 113.7-mm2, which is the same die size as our conventional DRAM, has been achieved with 0.50-µm CMOS process technology.

In this note, we consider the problem of finding a step-by-step transformation between two longest increasing subsequences in a sequence, namely LONGEST INCREASING SUBSEQUENCE RECONFIGURATION. We give a polynomial-time algorithm for deciding whether there is a reconfiguration sequence between two longest increasing subsequences in a sequence. This implies that INDEPENDENT SET RECONFIGURATION and TOKEN SLIDING are polynomial-time solvable on permutation graphs, provided that the input two independent sets are largest among all independent sets in the input graph. We also consider a special case, where the underlying permutation graph of an input sequence is bipartite. In this case, we give a polynomial-time algorithm for finding a shortest reconfiguration sequence (if it exists).