Displaying similar documents to “The complexity of lexicographic sorting and searching”

Uniform distribution modulo one and binary search trees

Michel Dekking, Peter Van der Wal (2002)

Journal de théorie des nombres de Bordeaux

Similarity:

Any sequence x = ( x k ) k = 1 ∞ of distinct numbers from [0,1] generates a binary tree by storing the numbers consecutively at the nodes according to a left-right algorithm (or equivalently by sorting the numbers according to the Quicksort algorithm). Let H n ( x ) be the height of the tree generated by x 1 , ⋯ , x n . Obviously log n log 2 - 1 ≤ H n ( x ) ≤ n - 1 . If the sequences x are generated by independent random variables having the uniform distribution on [0, 1], then it is well known that there exists c > 0 such that...

A backward selection procedure for approximating a discrete probability distribution by decomposable models

Francesco M. Malvestuto (2012)

Kybernetika

Similarity:

Decomposable (probabilistic) models are log-linear models generated by acyclic hypergraphs, and a number of nice properties enjoyed by them are known. In many applications the following selection problem naturally arises: given a probability distribution p over a finite set V of n discrete variables and a positive integer k , find a decomposable model with tree-width k that best fits p . If ℋ is the generating hypergraph of a decomposable model and p ℋ is the estimate of p under the model,...

Spanning caterpillars with bounded diameter

Ralph Faudree, Ronald Gould, Michael Jacobson, Linda Lesniak (1995)

Discussiones Mathematicae Graph Theory

Similarity:

A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most c n 3 / 4 (at most n).

Closure for spanning trees and distant area

Jun Fujisawa, Akira Saito, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with d e g G u + d e g G v ≥ n - 1 , G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on d e g G u + d e g G v and the structure of the distant area for u and v. We prove...

A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays

Aziz Moukrim, Djamal Rebaine, Mehdi Serairi (2014)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this paper we consider the problem of scheduling, on a two-machine flowshop, a set of unit-time operations subject to time delays with respect to the makespan. This problem is known to be 𝒩 P x1d4a9;x1d4ab; -hard in the strong sense. We propose an algorithm based on a branch and bound enumeration scheme. This algorithm includes the implementation of new lower and upper bound procedures, and dominance rules. A computer simulation to measure the performance of the algorithm is provided...

The color-balanced spanning tree problem

Štefan Berežný, Vladimír Lacko (2005)

Kybernetika

Similarity:

Suppose a graph G = ( V , E ) whose edges are partitioned into p disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories. We show that polynomiality of this problem depends on the number p of categories and present some polynomial algorithm.

On the weighted Euclidean matching problem in ℝ d

Birgit Anthes, Ludger Rüschendorf (2001)

Applicationes Mathematicae

Similarity:

A partitioning algorithm for the Euclidean matching problem in ℝ d is introduced and analyzed in a probabilistic model. The algorithm uses elements from the fixed dissection algorithm of Karp and Steele (1985) and the Zig-Zag algorithm of Halton and Terada (1982) for the traveling salesman problem. The algorithm runs in expected time n ( l o g n ) p - 1 and approximates the optimal matching in the probabilistic sense.