Sequential access in splay trees takes linear time

Sleator and Tarjan have invented a form of self-adjusting binary search tree called thesplay tree. On any sufficiently long access sequence, splay trees are as efficient, to within a constant factor, as both dynamically balanced and static optimum search trees. Sleator and Tarjan have made a much stronger conjecture; namely, that on any sufficiently long access sequence and to within a constant factor, splay trees are as efficient asany form of dynamically updated search tree. Thisdynamic optimality conjecture implies as a special case that accessing the items in a splay tree in sequential order takes linear time, i.e.O(1) time per access. In this paper we prove this special case of the conjecture, generalizing an unpublished result of Wegman. Oursequential access theorem not only supports belief in the dynamic optimality conjecture but provides additional insight into the workings of splay trees. As a corollary of our result, we show that splay trees can be used to simulate output-restricted deques (double-ended queues) in linear time. We pose several open problems related to our result.     

Bin packing can be solved within 1 + ε in linear time

For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive ε, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L)/L*≦1+ε for anyL providedL* is sufficiently large. The work of this author was supported by NSF Grant MCS 70-04997.     

Eigenvalues,geometric expanders,sorting in rounds,and ramsey theory

Expanding graphs are relevant to theoretical computer science in several ways. Here we show that the points versus hyperplanes incidence graphs of finite geometries form highly (nonlinear) expanding graphs with essentially the smallest possible number of edges. The expansion properties of the graphs are proved using the eigenvalues of their adjacency matrices. These graphs enable us to improve previous results on a parallel sorting problem that arises in structural modeling, by describing an explicit algorithm to sortn elements ink time units using parallel processors, where, e.g., α₂=7/4, α₃=8/5, α₄=26/17 and α₅=22/15. Our approach also yields several applications to Ramsey Theory and other extremal problems in combinatorics.     

Alternating cycle-free matchings

The investigation of alternating cycle-free matchings is motivated by the Jump-number problem for partially ordered sets and the problem of counting maximum cardinality matchings in hexagonal systems.We show that the problem of deciding whether a given chordal bipartite graph has an alternating cycle-free matching of a given cardinality is NP-complete. A weaker result, for bipartite graphs only, has been known for some time. Also, the alternating cycle-free matching problem remains NP-complete for strongly chordal split graphs of diameter 2.In contrast, we give algorithms to solve the alternating cycle-free matching problem in polynomial time for bipartite distance hereditary graphs (time O(m ²) on graphs with m edges) and distance hereditary graphs (time O(m ⁵)).     

Computing the bump number is easy

The bump number b(P) of a partial order P is the minimum number of comparable adjacent pairs in some linear extension of P. It has an interesting application in the context of linear circuit layout problems. Its determination is equivalent to maximizing the number of jumps in some linear extension of P, for which the corresponding minimization problem (the jump number problem) is known to be NP-hard. We derive a polynomial algorithm for determining b(P). The proof of its correctness is based on a min-max theorem involving simple-structured series-parallel partial orders contained in P. This approach also leads to a characterization of all minimal partial orders (with respect to inclusion of the order relations) with fixed bump number.Supported by Sonderforschungsbereich 303 of the University of Bonn.Supported by DAAD and SSHRC, Grant No. 451861295.     

How to make a digraph strongly connected

Given a directed graphG, acovering is a subsetB of edges which meets all directed cuts ofG. Equivalently, the contraction of the elements ofB makesG strongly connected. AnO(n ⁵) primal-dual algorithm is presented for finding a minimum weight covering of an edge-weighted digraph. The algorithm also provides a constructive proof for a min-max theorem due to Lucchesi and Younger and for its weighted version.     

An Ω(n 5/4) lower bound on the randomized complexity of graph properties

A decision tree algorithm determines whether an input graph withn nodes has a property by examining the entries of the graph's adjacency matrix and branching according to the information already gained. All graph properties which are monotone (not destroyed by the addition of edges) and nontrivial (holds for somes but not all graphs) have been shown to require (n ²) queries in the worst case.In this paper, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next entry to be examined. The complexity of a randomized algorithm is the expected number of entries that are examined in the worst case. The randomized complexity of a property is the minimum complexity of any randomized decision tree algorithm which computes the property. We improve Yao's lower bound on the randomized complexity of any nontrivial monotone graph property from (n log^1/12 n) to (n ^5/4).     

The monotone circuit complexity of boolean functions

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of sizes in a graphm vertices requires monotone circuits of size Ω(m ^s /(logm)^2s ) for fixeds, and sizem ^Ω(logm) form/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/logm)^2/3 requires monotone circuits exp (Ω((m/logm)^1/3)). For fixeds, any monotone circuit that detects cliques of sizes requiresm) ^s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function ofn variables is exp (Ω(n ^1/4 · (logn)^1/2)), improving a recent result of exp (Ω(n ^1/8-ε)) due to Andreev. First author supported in part by Allon Fellowship, by Bat Sheva de-Rotschild Foundation by the Fund for basic research administered by the Israel Academy of Sciences. Second author supported in part by a National Science Foundation Graduate Fellowship.     

A strongly polynomial minimum cost circulation algorithm

A new algorithm is presented for the minimum cost circulation problem. The algorithm is strongly polynomial, that is, the number of arithmetic operations is polynomial in the number of nodes, and is independent of both costs and capacities.     

On the average oscillation of a stack

Evaluating a binary tree in postorder we assume that in one unit of time zero or two nodes are removed from the top of the stack and one node is stored in the stack. The oscillation of the stack can be described by a functionf wheref(t) is the number of nodes in the stack aftert units of time. In this paper we shall first derive several new enumeration results concerning planted plane trees. In the second part we shall prove, that the average number of maxima (MAX-turns) and minima (MIN-turns) of the functionf isn/2 andn/2—1, respectively, provided that all binary trees withn leaves are equally likely. Finally, we shall compute for largen and fixedj the average increase (decrease) of the length of the stack between thej-th MIN-turn and (j+1)-th MAX-turn (between thej-th MAX-turn and thej-th MIN-turn). This result implies that the average oscillation of the stack can be described by the functionf(j)=4√j/π−(−1) ^j +O(1/√j) for largen and fixed turn-numberj.     

On the average hyperoscillations of planted plane trees

Assume that the leaves of a planted plane tree are enumerated from left to right by 1, 2, .... Thej-ths-turn of the tree is defined to be the root of the (unique) subtree of minimal height with leavesj, j+1, ...,j+s−1. If all trees withn nodes are regarded equally likely, the average level number of thej-ths-turn tends to a finite limitα _s (j), which is of orderj ^1/2. Thej-th ”s-hyperoscillation”α ₁(j)−α _s+1(j) is given by 1/2α ₁(s)+O(j ^−1/2) and therefore tends (forj → ∞) to a constant behaving like √8/π·s ^1/2 fors → ∞. These results are obtained by setting up appropriate generating functions, which are expanded about their (algebraic) singularities nearest to the origin, so that the asymptotic formulas are consequences of the so-called Darboux-Pólyamethod.     

The complexity of detecting crossingfree configurations in the plane

The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.Klaus Jansen acknowledges support by the Deutsche Forschungsgemeinschaft. Gerhard J. Woeginger acknowledges support by the Christian Doppler Laboratorium für Diskrete Optimierung.     

How to draw a planar graph on a grid

Answering a question of Rosenstiehl and Tarjan, we show that every plane graph withn vertices has a Fáry embedding (i.e., straight-line embedding) on the 2n–4 byn–2 grid and provide anO(n) space,O(n logn) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any setF, which can support a Fáry embedding of every planar graph of sizen, has cardinality at leastn+(1–o(1))n which settles a problem of Mohar.Supported in part by P. R. C. Mathematiques et Informatique.Supported in part by HSF grant 1814.Part of the work on this paper was done while this author was on sabbatical leave at école Normal Supérieure and école des Hautes études en Sciences Sociales; supported in part by NSF grant DMS-850 1947.     

An analysis of the greedy algorithm for the submodular set covering problem

We consider the problem: min \(\{ \mathop \Sigma \limits_{j \in s} f_j :z(S) = z(N),S \subseteqq N\} \) wherez is a nondecreasing submodular set function on a finite setN. Whenz is integer-valued andz(Ø)=0, it is shown that the value of a greedy heuristic solution never exceeds the optimal value by more than a factor \(H(\mathop {\max }\limits_j z(\{ j\} ))\) where \(H(d) = \sum\limits_{i = 1}^d {\frac{1}{i}} \) . This generalises earlier results of Dobson and others on the applications of the greedy algorithm to the integer covering problem: min {fy: Ay ≧b, y ε {0, 1}} wherea _ij ,b _i } ≧ 0 are integer, and also includes the problem of finding a minimum weight basis in a matroid.     

Disjoint paths in a rectilinear grid

We give a good characterization and a good algorithm for a special case of the integral multicommodity flow problem when the graph is defined by a rectangle on a rectilinear grid. The problem was raised by engineers motivated by some basic questions of constructing printed circuit boards.     

An algorithm for finding hamilton paths and cycles in random graphs

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs withn vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending to 1, asn tends to ∞. Various modifications of HAM are shown to solve several Hamilton path problems. Supported by NSF Grant MCS 810 4854.     

The struction of a graph: Application toCN-free graphs

We consider the class of graphs characterized by the forbidden subgraphsC andN:C is the claw (unique graph with degree sequence (3, 1, 1, 1)) andN the net (unique graph with degree sequence (3, 3, 3, 1, 1, 1)). For this class of graphs (calledCN-free) an algorithm is described for determining the stability numberα(G). It is based on a construction associating with anyCN-free graphG anotherCN-free graphG′ such thatα(G′)=α(G)−1. Such a construction reducing the stability number is called a struction. This work was completed while this author was visiting the Dept. of Combinatories and Optimization at the University of Waterloo, Ontario.     

Fcfs-scheduling in a hard real-time environment under rush-hour conditions

We investigate some real-time behaviour of a (discrete time) single server system with FCFS (first come first serve) task scheduling under rush-hour conditions. The main result deals with the probability distribution of a random variable SRD(T), which describes the time the system operates without violating a fixed task service time deadlineT.Relying on a simple general probability model, asymptotic formulas concerning the mean and the variance of SRD(T) are determined; for instance, if the average arrival rate is larger than the departure rate, the expectation of SRD(T) is proved to fulfilE[SRD(T)]=c ₁+O(T ^–3) forT, wherec ₁ denotes some constant. If the arrival rate equals the departure rate, we findE[SRD(T)]c ₂ T ⁱ for somei2.     

Paired domination on interval and circular-arc graphs

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time.     

An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem*

Given an undirected multigraph G and a subset of vertices S ⊆ V (G), the STEINER TREE PACKING problem is to find a largest collection of edge-disjoint trees that each connects S. This problem and its generalizations have attracted considerable attention from researchers in different areas because of their wide applicability. This problem was shown to be APX-hard (no polynomial time approximation scheme unless P=NP). In fact, prior to this paper, not even an approximation algorithm with asymptotic ratio o(n) was known despite several attempts. In this work, we present the first polynomial time constant factor approximation algorithm for the STEINER TREE PACKING problem. The main theorem is an approximate min-max relation between the maximum number of edge-disjoint trees that each connects S (S-trees) and the minimum size of an edge-cut that disconnects some pair of vertices in S (S-cut). Specifically, we prove that if every S-cut in G has at least 26k edges, then G has at least k edge-disjoint S-trees; this answers Kriesells conjecture affirmatively up to a constant multiple. * A preliminary version appeared in the Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2004. † The author was supported by an Ontario Graduate Scholarship and a University of Toronto Fellowship.