In a series of four papers we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$, every $n$-vertex graph $G$ with at least $(\frac{1}{2}+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. The method to prove our result follows a strategy similar to approaches that employ the Szemerédi regularity lemma: We decompose the graph $G$, find a suitable combinatorial structure inside the decomposition, and then embed the tree $T$ into $G$ using this structure. Since for sparse graphs $G$, the decomposition given by the regularity lemma is not helpful, we use a more general decomposition technique. We show that each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. In this paper, we introduce this novel decomposition technique. In the three follow-up papers, we find a suitable combinatorial structure inside the decomposition, which we then use for embedding the tree.

This is the second of a series of four papers in which we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$, every $n$-vertex graph $G$ with at least $(\frac{1}{2}+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first paper of this series, we gave a decomposition of the graph $G$ into several parts of different characteristics; this decomposition might be viewed as an analogue of a regular partition for sparse graphs. In the present paper, we find a combinatorial structure inside this decomposition. In the third and fourth papers, we refine the structure and use it for embedding the tree $T$.

This is the third of a series of four papers in which we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$, every $n$-vertex graph $G$ with at least $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first paper of the series, we gave a decomposition of the graph $G$ into several parts of different characteristics. In the second paper, we found a combinatorial structure inside the decomposition. In this paper, we will give a refinement of this structure. In the fourth paper, the refined structure will be used for embedding the tree $T$.

This is the last of a series of four papers in which we prove the following relaxation of the Loebl--Komlós--Sós conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$, every $n$-vertex graph $G$ with at least $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first two papers of this series, we decomposed the host graph $G$ and found a suitable combinatorial structure inside the decomposition. In the third paper, we refined this structure and proved that any graph satisfying the conditions of the above approximate version of the Loebl--Komlós--Sós conjecture contains one of ten specific configurations. In this paper we embed the tree $T$ in each of the ten configurations.

Given a set of n nuts of distinct widths and a set of n bolts such that each nut corresponds to a unique bolt of the same width, how should we match every nut with its corresponding bolt by comparing nuts with bolts? (No comparison is allowed between two nuts or two bolts.) The problem can be naturally viewed as a variant of the classic sorting problem as follows. Given two lists of n numbers each such that one list is a permutation of the other, how should we sort the lists by comparisons only between numbers in different lists? We give an O(n log n)-time deterministic algorithm for the problem. This is optimal up to a constant factor and answers an open question posed by Alon et al. [Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, 1994, pp. 690--696]. Moreover, when copies of nuts and bolts are allowed, our algorithm runs in optimal O(log n) time on n processors in Valiant's parallel comparison tree model. Our algorithm is based on the AKS sorting algorithm with substantial modifications.

The authors investigate the asymptotic efficiency of certain combinatorial networks called halvers, which are basic building blocks of many parallel algorithms. They improve the efficiency of halvers in terms of their depth. The novelty is the use of combinatorial circuits whose basic units are k-sorter switches.>

This paper presents a comparison sorting algorithm for the abstract CROW PRAM parallel computer model. The algorithm sorts n input values using n processors and runs in time $O(\log n/\log \log n)$ on the average, assuming that all permutations of the input are equally likely.

The authors investigate how good connectivity properties translate into good error-correcting behavior in sparse networks of threshold elements. They determine how the eigenvalues of the interconnection graph (which in turn reflect connectivity properties) relate to the quantities, number of items stored, amount of error-correction, radius of attraction, and rate of convergence in an associative memory model consisting of a sparse network of threshold elements or neurons.>

In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n)2 / log log n passes the test with probability at least 1/n then a deterministic sequence can be constructed in LOGSPACE which also passes the test. It is important that the machine performing the test gets each bit of the sequence only once. The theorem remains valid if both the test and the machine constructing the satisfying sequence have access to the same oracle of polynomial size.

The first result concerns branching programs having width (log n) °{*).We give an fl(n log n~ log log n) lower bound for the size of such branching programs computing almost any symmetric Boolean fnnction and in particular the following explicit fnnction: "the sum of the input variables is a quadratic residue mod p" where p is any given prime between n 1/4 and n 1/3.This is a strengthening of previous nonlinear lower bounds obtained by Chandra, Furst, Lipton and by Pudlgk.We mention that by iterating our method the result can be further strengthened to lfl(nlog n).The second result is a C" lower bound for read-onceonly branching programs computing an explicit Boolean function.For n = (~), the function computes the parity of the number of triangles in a graph on v vertices.This improves previous exp(cx/n ) lower bounds for other graph functions by Wegener and Z£k.The result implies a linear lower bound for the space complexity of this Boolean function on "eraser machines", i.e. machines that erase each input bit immediately after having read it.

We show that in the deterministic comparison model for parallel computation, n processors can select the k th smallest item from a set of n numbers in O(loglogn) parallel time.With this result all comparison tasks (selection, merging, sorting), now have upper and lower bounds of the same order in both random and deterministic models.

Abstract Based on the probabilistic approach introduced by Karp [14], we present two partitioning algorithms for the approximate solution of large instances of the rectilinear Steiner problem in the plane. The algorithms subdivide a set of given points into small groups, construct a minimum rectilinear Steiner tree for each small group, and then patch the subtrees together to form a near‐optimum rectilinear Steiner tree for the given points. Suppose there are n given points, uniformly distributed over the unit square [0,1] × [0,1] and spanned by a minimum rectilinear Steiner tree To. Then for any given integer t > 0, the first algorithm runs in O(f(t)n + n log n) time and produces a rectilinear Steiner tree T1 such that \documentclass{article}\pagestyle{empty}\begin{document}$ \left({|T_1 |/|T_0 |} \right) \le 1 + O\left({\sqrt {1/t}} \right) $\end{document} with probability approaching 1 as n → ∞, while the second algorithm has an expected running time of O(g(t)n) and it also produces a rectilinear Steiner tree T2 such that \documentclass{article}\pagestyle{empty}\begin{document}$ \left({|T_2 |/|T_0 |} \right) \le 1 + O\left({\sqrt {1/t}} \right) $\end{document} with probability approaching 1 as n → ∞.

A basic problem in the decentralized control of a multiple access channel is to resolve the conflicts that arise when several stations transmit simultaneously to the channel. Capetanakis, Hayes, and Tsybakov and Mikhailov found a deterministic {\em tree algorithm} that resolves conflicts amongkstations from an ensemble ofnin time\Theta (k + k \log (n / k))in the worst case. In this algorithm, at each step, the choice of which stations to enable to transmit depends crucially on feedback information provided by the channel. We show that ifkis given {\em a priori} then such conflicts can be resolved in time\Theta (k + k \log (n / k))using an algorithm in which the corresponding choices do not depend on feedback.

Given a rooted tree with values associated with the n vertices and a set A of directed paths (queries), we describe an algorithm which finds the maximum value of every one of the given paths, and which uses only 5n + n log [(|A|+n)/n] comparisons. This leads to a spanning tree verification algorithm using O(n+e) comparisons in a graph with n vertices and e edges. No implementation is offered.

A data structure for representing a set of n items from a umverse of m items, which uses space n + o(n) and accommodates membership queries m constant time is described.Both the data structure and the query algorithm are easy to ~mplement.

The complexity of priority queue operations is analyzed with respect to the cell probe computational model of A. Yao. A method utilizing families of hash functions is developed which permits priority queue operations to be implemented in constant worst case time provided that a size constraint is satisfied. The minimum necessary size of a family of hash functions for computing the rank function is estimated and contrasted with the minimum size required for perfect hashing.

The purpose of this paper is to describe a sorting network of size 0(n log n) and depth 0(log n).

We describe a data structure for representing a set of n items from a universe of m items, which uses space n+o(n) and accommodates membership queries in constant time. Both the data structure and the query algorithm are easy to implement.