27124060
The Complexity of Finding Certain Trees in Tournaments
A tournament Tn is an orientation of the complete graph on n vertices. We continue the algorithmic study initiated by Hell and Rosenfeld[5] of recognizing various directed trees in tournaments. Hell and Rosenfeld considered orientations of paths, and showed the existence of oriented paths on n vertices finding which in Tn requires Θ(n lgα n) “edge probes” where α ≤ 1 is any fixed non-negative constant. Here, we investigate the complexity of finding a vertex of prescribed outdegree (or indegree). In particular, we show, by proving upper and lower bounds, that the complexity of finding a vertex of outdegree k(n−1)/2) in Tn is Θ(nk). We also establish an Ω(n2) lower bound for finding a vertex of maximum outdegree in Tn. These bounds are in sharp contrast to the O(n) bounds for selection in the case of transitive tournaments.
38155628
Tight Bounds for Finding Degrees from the Adjacency Matrix
King and Smith-Thomas[5] have shown that to find a sink (a vertex with outdegree 0 and indegree n−1) in an n vertex directed graph, 3n-⌊log n⌋-3 probes to its adjacency matrix are necessary and sufficient in the worst case. We first generalize this result to show that for any integer k between 0 and n−1, 
 
 
to find a vertex of outdegree k in a simple n vertex directed graph, Θ(n(n−k)) probes to its adjacency matrix are necessary and sufficient in the worst case, and 
 
 
to find a vertex of degree k in an n vertex undirected graph, Θ(n2) probes to its adjacency matrix are necessary and sufficient in the worst case.
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.
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.
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.
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.
9665741
Soft-output detection of CPM signals in frequency flat, Rayleigh fading channels
Symbol-by-symbol detection algorithms are useful in systems in which soft-decision metrics are important, e.g., systems with interleaved coded modulation. A soft-output algorithm for the detection of continuous phase modulated (CPM) signals transmitted over frequency flat, Rayleigh fading channels is developed. Since the optimum detector is computationally too complex for any practical implementation, some suboptimal detectors which give near optimal performance are proposed. Some theoretical approximations for the performance of the interleaved coded system are given. The performance of the soft-output algorithms is also extensively characterized by means of Monte-Carlo simulations.
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.
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.
13457273
A new Contrast Based Image Fusion using Wavelet Packets
Image Fusion, a technique which combines complimentary information from different images of the same scene so that the fused image is more suitable for segmentation, feature extraction, object recognition and Human Visual System. In this paper, a simple yet efficient algorithm is presented based on contrast using wavelet packet decomposition. First, all the source images are decomposed into low and high frequency sub-bands and then fusion of high frequency sub-bands is done by the means of Directive Contrast. Now, inverse wavelet packet transform is performed to reconstruct the fused image. The performance of the algorithm is carried out by the comparison made between proposed and existing algorithm.