Abstract We exhibit an algorithm for finding a maximum independent set (MIS) for n presorted, unweighted circular arcs in time 0(n). Unlike previous algorithms, this is achieved by means of trivial postprocessing of the output of a straightforward algorithm for finding an MIS for a set of unweighted intervals. © 2002 Wiley Periodicals, Inc.

We present a simple $O(n)$ time and space algorithm for producing a domatic partition and the domatic number for members of the class of interval graphs, where n is the number of intervals in a graph.

In 1979, G. K. Manacher showed that the Ford-Johnson sorting algorithm [FJA], acting on t real numbers, can be beaten for an infinite set of values t . These values form a partial cover of constant density not close to 1 over an initial sequence of each band running from u k = ⌊(4/3)2 k ⌋ to u k +l - 1. This early result depended on showing that the Hwang-Lin merging algorithm [HLA], merging m elements with n , m ≠ n , could be surpassed by cm comparisons, where c is an arbitrary small positive constant. In this paper, it is shown that the FJA can be beaten for a set of integers of asymptotic density 1 under the greatly weakened assumption that the HLA can be surpassed by only (1/2 + ϵ)log m comparisons, with ϵ a small positive constant. The even weaker assumption that no improvement in the HLA exists, but that an isolated value t o exists for which the FJA can be surpassed by only (1 + ϵ)log t o comparisons yields the same result. Only for a set of “refractory” integers of size about t 1/2 in the neighborhood of each u k does the FJA fail to be beaten. All these results depend on a new technique for obtaining optimum sort-merge sequences for best-possible sorting given a merging method. The technique turns out to be amenable to precise asymptotic analysis. When the technique is applied using the most powerful known merging algorithm [Christen's], the density mentioned above is still 1, but islands of refractory points still remain, this time forming sets provably of size Θ(log 2 t ) in the neighborhood of each u k . It is shown that if “information theoretic” merging were achievable, the FJA could be beaten for all t > u 10 = 1365. From these results and a few others, we adduce evidence in support of our main conjecture: that even optimum combinations of optimum merging and Ford-Johnson sorting will not beat the FJA when t = u k , but will instead produce refractory regions of size Θ(log 2 t ) in the neighborhood of each λ .

The Hwang-Lin mergmg algorithm is the best general-purpose merging algorithm that has been found Many improvements to ~t have been devtsed, but these are etther for special values of m and n, the number of ~tems being merged, or else zmprovements by a term less than hnear m n + m when the ratm n/m ~s fixed A new methodology is developed m which, for fixed ratio n/m, It ts possible to decrease the number of comparisons by a factor proporUonal to m, m fact m/12, provided n/m _> 8 and m >_ 24 It is shown that the coefficient ~s not best possible, and a techmque for lmprowng it shghtly to ~ is sketched

One way of expressing the efficiency of a sorting algorithm is m terms of the number of palrwise comparisons required in the worst case to sort t items The most effioent algomhm known is that of Ford and Johnson [FJA], which achieves the "information-theoretic" lower bound [log t I] for l --< t _< I l and 21 _< t _< 22 No value of t has been discovered for which S(t) < F(t), where S(t) is the smallest number of comparisons required and F(t) is the number of comparisons required by the FJA It has been uncertain since the FJA first appeared in 1959 whether it is optimal in the sense that F(t) = S(t) for all t It is shown that this is not the case, and it ts shown constructively how to compute infinitely many t, t _> 189, for which F(t) -S(t) = kt -O(log t) for posiuve k The method is intimately related to the fact that substantial improvements to the merging algorithm of Hwang and Lm are possible, as shown in a companion paper.

A less general model of Codd's relational model is proposed, for which queries and updates are maximally efficient. The differences in access method from Codd's are minor enough so that almost all the compactness of expression and quality of data independence remains.

Despite significant advances in linear-time scanning algorithms, particularly those based wholly or in part on either Cook's linear-time simulation of two-way deterministic pushdown automata or Weiner's algorithm, the problem of recognizing the initial leftmost nonvoid palindrome of a string in time proportional to the length N of the palindrome, examining no symbols other than those in the palindrome, has remained open.The present algorithm solves this problem, assuming that addition of two integers less than or equal to N may be performed in a single operation.Like the Knuth-Morris-Pratt algorithm, it runs in time independent of the size of the input alphabet.The algorithm as presented finds only even palindromes.However, an extension allows one to recognize the initial odd or even palindrome of length 2 or greater.Other easy extensions permit the recognition of strings (wwR) * of even palindromes and of all the initial palindromes.It appears possible that further extension may be used to show that (wwR) * is in a sense recognizable in real time on a reasonably defined random access machine.

A model for multiprocessor control is considered in which jobs are broken into various pieces, called tasks . Tasks are executed by single processing units. In this paper the structure controlling the assignment of tasks to processors is the task list, which orders all tasks according to servicing priority. When a processors becomes free, it simply picks up the highest priority task that is executable at that moment. The job and its component tasks are imagined to be interacting with an environment consisting of a set of rigid timing constraints . Such constraints are of two types, called start-times and deadlines . The interaction is specified by requiring that certain distinguished tasks conform directly to one or more of these constraints. Tasks conforming to a start-time cannot begin until the start-time has passed, and tasks conforming to a deadline cannot proceed beyond the deadline. In our model, all tasks have known maximum run-times, but in any particular job execution, task run-times are unknown. It is shown that despite the simplicity of this control scheme some peculiar phenomena result. Most of these phenomena were first noticed by P. Richards in 1960. A simulation study (Appendix I) reveals that they may be very common in practice. In the present paper and a companion paper by R. L. Graham [ Bell Syst. Tech. J. 45 (1966), 1563-1581] a coherent theory of task-list control is developed, in which the nature of these peculiarities is brought under systematic study. A number of potentially useful results are derived.