Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
The computational complexity of the criticality problems in a network with interval activity times
2002
Abstract The paper analyzes the criticality in a network with interval activities duration times. A natural generalization of the criticality notion (for a path, an activity and an event) for the case of network with interval activity duration times is given. The computation complexity of five problems linked to the introduced criticality notion is presented.
On the low-dimensional Steiner minimum tree problem in Hamming metric
2013
While it is known that the d-dimensional Steiner minimum tree problem in Hamming metric is NP-complete if d is part of the input, it is an open question whether this also holds for fixed dimensions. In this paper, this question is answered by showing that the Steiner minimum tree problem in Hamming metric is already NP-complete in 3 dimensions. Furthermore, we show that, the minimum spanning tree gives a 2-2d approximation on the Steiner minimum tree for d>=2. Using this result, we analyse the so-called k-LCA and A"k approximation algorithms and show improved approximation guarantees for low dimensions.
Symmetric (79, 27, 9)-designs Admitting a Faithful Action of a Frobenius Group of Order 39
1997
AbstractIn this paper we present the classification of symmetric designs with parameters (79, 27, 9) on which a non-abelian group of order 39 acts faithfully. In particular, we show that such a group acts semi-standardly with 7 orbits. Using the method of tactical decompositions, we are able to construct exactly 1320 non-isomorphic designs. The orders of the full automorphism groups of these designs all divide 8 · 3 · 13.
Automata and differentiable words
2011
We exhibit the construction of a deterministic automaton that, given k > 0, recognizes the (regular) language of k-differentiable words. Our approach follows a scheme of Crochemore et al. based on minimal forbidden words. We extend this construction to the case of C\infinity-words, i.e., words differentiable arbitrary many times. We thus obtain an infinite automaton for representing the set of C\infinity-words. We derive a classification of C\infinity-words induced by the structure of the automaton. Then, we introduce a new framework for dealing with \infinity-words, based on a three letter alphabet. This allows us to define a compacted version of the automaton, that we use to prove that ev…
Embedding finite linear spaces in projective planes, II
1987
Abstract It is shown that a finite linear space with maximal point degree n + 1 can be embedded in a projective plane of order n, provided that the line sizes are big enough.
Finite linear spaces in which any n-gon is euclidean
1986
Abstract An n-gon of a linear space is a set S of n points no three of which are collinear. By a diagonal point of S we mean a point p off S with the property that at least two lines through p intersect S in two points. The number of diagonal points is called the type of S. For example, a 4-gon has at most three diagonal points. We call an n-gon euclidean if (roughly speaking) it contains the maximal possible number of 4-gons of type 3. In this paper, we characterize all finite linear spaces in which, for a fixed number n ⩾ 5, any n-gon is euclidean. It turns out that these structures are essentially projective spaces or punctured projective spaces.
Best Proximity Point Results in Non-Archimedean Fuzzy Metric Spaces
2013
We consider the problem of finding a best proximity point which achieves the minimum distance between two nonempty sets in a non-Archimedean fuzzy metric space. First we prove the existence and uniqueness of the best proximity point by using di fferent contractive conditions, then we present some examples to support our best proximity point theorems.
Balls into non-uniform bins
2014
Balls-into-bins games for uniform bins are widely used to model randomized load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks, which are not able to perfectly balance the load over the bins. While previous evaluations try to find strategies for uniform bins under non-uniform bin selection probabilities, this paper investigates heterogeneous bins, where the "capacities" of the bins might differ significantly. We show that heterogeneous environments can even help to distribute the load more eve…
A Motzkin filter in the Tamari lattice
2015
The Tamari lattice of order n can be defined on the set T n of binary trees endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we restrict our attention to the subset M n of Motzkin trees. This set appears as a filter of the Tamari lattice. We prove that its diameter is 2 n - 5 and that its radius is n - 2 . Enumeration results are given for join and meet irreducible elements, minimal elements and coverings. The set M n endowed with an order relation based on a restricted rotation is then isomorphic to a ranked join-semilattice recently defined in Baril and Pallo (2014). As a consequence, we deduce an upper bound for the rotation distan…
Generating binary trees by Glivenko classes on Tamari lattices
2003
Using algebraic-theoretic results, we give an algorithm for generating binary trees within Glivenko classes in Tamari lattices. Tamari lattices are lattices of binary trees endowed by the well-known rotation transformation.