2899394
An Improved Fixed-Parameter Algorithm for Vertex Cover
The Vertex Cover problem asks, for input consisting of a graph G on n vertices, and a positive integer k, whether there is a set of k vertices such that every edge of G is incident with at least one of these vertices. We give an algorithm for this problem that runs in time O(kn + (1.324718)kk2). In particular, this gives an O((1.324718)nn2) algorithm to find the minimum vertex cover in the graph.
27625864
Path Balance Heuristic for Self-Adjusting Binary Search Trees
In (A. Subramanian, An Explanation of Splaying, Proceedings of the 14th Foundations of Software Technology and Theoretical Computer Science, LNCS Springer Verlag 880 354–365), D. Sleator suggested the following heuristic for self adjusting binary search trees: Every time an access is made, restructure the entire path from the root of the search tree to the accessed node into a balanced binary search tree on those nodes, and place all other subtrees rooted at the children of the nodes in the access path in their proper positions. We show that the method has an O(log n log log n/ log log log n) amortized complexity.
119712961
On ideal-function-like functions
The aim of this paper is to extend the considerations of the first and the third authors and others to the setting of Suetuna, i.e. we consider some important sums of multiplicative ideal-functions in relative extensions of number fields. This contains most of the earlier work on those sums related to the divisor and the circle problems.
6028662
The Least Witness of a Composite Number
We consider the problem of finding the least witness of a composite number. If n is a composite number then a number w for which n is not a strong pseudo-prime to the base w is called a witness for n. Let w(n) be the least witness for a composite n. Bach [7] assuming the Generalized Riemann Hypothesis (GRH) showed that w(n) < 2log2 n. In this paper we are interested in obtaining upper bounds for w(n) without assuming the GRH.
5346923
Finding Scores in Tournaments
A tournamentTnis an orientation of the complete graph onnvertices. We continue the algorithmic study initiated by10of recognizing various directed trees in tournaments. Hell and Rosenfeld studied the complexity of finding various oriented paths in tournaments by probing edge directions. Here, we investigate the complexity of finding a vertex of prescribed outdegree (or indegree) in the same model. We show that the complexity of finding a vertex of outdegreek(?(n?1)/2) inTnis ?(nk). This bound is in sharp contrast to the ?(n) bound for selection in the case of transitive tournaments. We also establish tight bounds for finding vertices of prescribed degree from the adjacency matrix of general directed/undirected graphs. These bounds generalize the classical bound of11for finding a sink (a vertex of outdegree 0 and indegreen?1) in a directed graph.
8028128
Maximal Sets of Integers with Distinct Divisors
A set of positive integers is said to have the distinct divisor property if there is an injective map that sends every integer in the set to one of its proper divisors. In 1983, P. Erdős and C. Pomerance showed that for every $c>1$, a largest subset of $[N,cN]$ with the distinct divisor property has cardinality $\sim \delta(c)N$, for some constant $\delta(c)>0$. They conjectured that $\delta(c)\sim c/2$ as $c \to \infty$. We prove their conjecture. In fact we show that there exist positive absolute constants $D_1,D_2$ such that $D_1\le c^{\beta}(c/2-\delta(c))\le D_2$ where $\beta = \log 2/\log (3/2)$.
95165110
A comparison of techniques for nondestructive composition measurements in CdZnTe substrates
We report an overview and a comparison of nondestructive optical techniques for determining alloy composition x in Cd1-xZnxTe substrates for HgCdTe epitaxy. The methods for single-point measurements include a new x-ray diffraction technique for precision lattice parameter measurements using a standard highresolution diffractometer, room-temperature photoreflectance, and low-temperature photoluminescence. We compare measurements on the same set of samples by all three techniques. Comparisons of precision and accuracy, with a discussion of the strengths and weaknesses of different techniques, are presented. In addition, a new photoluminescence excitation technique for full-wafer imaging of composition variations is described.
28896383
Colorimetric modeling of binary color printers
Colorimetric device models play an important role in achieving consistent and accurate color reproduction among digital output devices. Models based on the Neugebauer (1937) mixing equations are examined for halftone color printers. Spectral information, and the Yule-Neilsen (1951) correction for light scattering, are incorporated into the models. A cellular approach is examined as a tradeoff between model accuracy and complexity. Two halftone screen orientations are discussed: the rotated or random dot; and the dot-on-dot configuration. Results show that the models can predict the printer response with acceptable accuracy.