Discrete Mathematics and Theoretical Computer Science

Secret sharing has been a subject of study for over twenty years, and has had a number of real-world applications. There are several approaches to the construction of secret sharing schemes. One of them is based on coding theory. In principle, every linear code can be used to construct secret sharing schemes. But determining the access structure is very hard as this requires the complete characterisation of the minimal codewords of the underlying linear code, which is a difficult problem. In this paper we present a sufficient condition under which we are able to determine all the minimal codewords of certain linear codes. The condition is derived using exponential sums. We then construct some linear codes whose covering structure can be determined, and use them to construct secret sharing schemes with interesting access structures.

It is widely anticipated that the study of variation in the human genome will provide a means of predicting risk of a variety of complex diseases. This paper presents a number of algorithmic and combinatorial problems that arise when studying a very common form of genomic variation, single nucleotide polymorphisms (SNPs). We review recent results and present challenging open problems.

The first paper on cellular automata in the hyperbolic plane appeared in [37], based on the technical report [35]. Later, several papers appeared in order to explore this new branch of computer science. Although applications are not yet seen, they may appear, especially in physics, in the theory of relativity or for cosmological researches.

We give a definition of Gray code that, unlike the standard “minimal change” definition, is satisfied by the word-lists in the literature called “Gray codes” and we give several examples to illustrate the various concepts of minimality. We show that a non-recursive generation algorithm can be obtained for a word-list such that all the words with the same prefix (or, equivalently, suffix) are consecutive and that the Bitner-Ehrlich-Reingold method of generating each word in a time bounded by a constant works under the additional condition that in the interval of words with the same prefix or suffix the next letter assumes at least two values. Finally we generalize this method so that it works under a weaker condition satisfied by almost all the Gray codes in the literature: if the next letter assumes only one value, then the interval contains only one word.

We present an O(nv) Basis Oriented Pivoting (BOP) algorithm for enumerating vertices of simple polyhedra associated with dual LI(2) systems. The algorithm is based on a characterisation of their graphical basis structures, whose set of edges are shown to consist of vertex-disjoint components that are either a tree or a subgraph with only one cycle. The algorithm generates vertices via operations on the basis graph, rather than by simplex transformations.

Algorithmic and resource-bounded Baire category and corresponding genericity concepts introduced in computability theory and computational complexity theory, respectively, have become elegant and powerful tools in these settings. Here we introduce some new genericity notions based on extension functions computable by finite automata which are tailored for capturing diagonalizations over regular sets and functions. We show that the generic sets obtained either by the partial regular extension functions of any fixed constant length or by all total regular extension of constant length are just the sets with saturated (also called disjunctive) characteristic sequence α. Here a sequence α is saturated if every string occurs in α as a substring. We also show that these automatic generic sets are not regular but may be context free. Furthermore, we introduce stronger automatic genericity notions based on regular extension functions of nonconstant length and we show that the corresponding generic sets are bi-immune for the class of regular and context free languages.

The order-bounded linear functionals on a Rieszs pace are investigated constructively. Two classically equivalent notions of positivity for linear functionals, and their relation to the strong extensionality, are examined. A necessary and sufficient condition for the existence of the supremum of two elements of the order dual of a Rieszs pace with unit is obtained.

It was known that every graph can be constructed from a finite list of elementary graphs using the operations of graph sum and graph composition. We determine a complete set of “equations” or rewriting rules with the property that two expressions represent the same graph if and only if one can be transformed into the other by means of these rules.

ECO is a method for the enumeration of classes of combinatorial objects based on recursive constructions of such classes. In this paper we use the ECO method and the concept of succession rule to develop an algorithm for the exhaustive generation of convex polyominoes. Then we prove that this algorithm runs in constant amortized time.

We give a class of timed regular expressions that involve the use of colored parentheses for specifying timing constraints. The expressions are given in a matricial format, and their semantics is based upon an “overlapping concatenation” of timed words. We then give a calculus for emptiness checking of a regular expression, that does not go through translating expressions into timed automata. To this end we use the class of 2n-automata, studied in a parallel paper [Dim02] in connection with the problem of representing timing constraints.

We prove in this paper that there exists some infinitary rational relations which are Σ ₃ ⁰ -complete Borel sets and some others which are Π ₃ ⁰ -complete. These results give additional answers to questions of Simonnet [Sim92] and of Lescow and Thomas [Tho90,LT94].

In this note, the problem of determining disjoint matchings in a set of intervals is investigated (two intervals can be matched if they are disjoint). Such problems find applications in schedules planning. First, we propose a new incremental algorithm to compute maximum disjoint matchings among intervals. We show that this algorithm runs in O(n) time if the intervals are given ordered in input. Additionally, a shorter algorithm is given for the case where the intervals are proper. Then, a NP-complete extension of this problem is considered: the perfect disjoint multidimensional matching problem among intervals. A sufficient condition is established for the existence of such a matching. The proof of this result yields a linear-time algorithm to compute it in this case. Besides, a greedy heuristic is shown to solve the problem in linear time for proper intervals.

We present a uniform definition for classes of single- and multi-valued functions. We completely analyze the inclusion structure of function classes. In order to compare classes of multi-valued and single-valued functions with respect to the existence of refinements we extend the so called operator method [VW93,HW00] to make it applicable to such cases. Our approach sheds new light on well-studied classes like NPSV and NPMV, allows to give simpler proofs for known results, and shows that the spectrum of function classes closely resembles the spectrum of well-known complexity classes.

In this paper, we will consider the problem of coloring directed paths on a mesh network. A natural application of this graph problem is WDM-routing in all-optical networks. Our main result is a simple 4-approximation algorithm for coloring line-column paths on a mesh. We also present sharper results when there is a restriction on the path lengths. Moreover, we show that these results can be extended to toroidal meshes and to line-column or column-line paths.

In this paper we consider a class of infinite one player games played on finite graphs. Our main questions are the following: given a game, how efficient is it to find whether or not the player wins the game?If the player wins the game, then how much memory is needed to win the game?F or a given number n, what does the underlying graph look like if the player has a winning strategy of memory size n?

The paper investigates relationship between algebraic expressions and graphs. Through out the paper we consider two kinds of digraphs: series-parallel graphs and Fibonacci graphs (which give a generic example of non-series-parallel graphs). Motivated by the fact that the most compact expressions of series-parallel graphs are read-once formulae, and, thus, of O(n) length, we propose an algorithm generating expressions of O(n ²) length for Fibonacci graphs.A serious effort was made to prove that this algorithm yields expressions with a minimum number of terms. Using an interpretation of a shortest path algorithm as an algebraic expression, a symbolic approach to the shortest path problem is proposed.

When studying complexity classes of partitions we often face the situation that different partition classes have the same component classes. The projective closures are the largest classes among these with respect to set inclusion. In this paper we investigate projective closures of classes of boolean NP-partitions, i.e., partitions with components that have complexity upper-bounds in the boolean hierarchy over NP. We prove that the projective closures of these classes are represented by finite labeled posets. We give algorithms for calculating these posets and related problems. As a consequence we obtain representations of the set classes NP(m) ∩ coNP(m) by means of finite labeled posets.

The stability number α(G) of the graph G is the size of a maximum stable set of G. If s _k denotes the number of stable sets of cardinality k in graph G, then \( I\left( {G;x} \right) = \sum\limits_{k = 0}^{\alpha \left( G \right)} {s_k x^k } \) is the independence polynomial of G (I. Gutman and F. Harary 1983). In 1990, Y.O. Hamidoune proved that for any claw-free graph G (a graph having no induced subgraph isomorphic to K _1,3), I(G; x) is unimodal, i.e., there exists some k ∈ {0, 1, ..., α(G)} such that Y. Alavi, P.J. Malde, A.J. Schwenk, and P. Erdös (1987) asked whether for trees the independence polynomial is unimodal. J . I. Brown, K. Dilcher and R.J. Nowakowski (2000) conjectured that I(G; x) is unimodal for any well-covered graph G (a graph whose all maximal independent sets have the same size). Michael and Traves (2002) showed that this conjecture is true for well-covered graphs with α(G) ≤ 3, and provided counterexamples for α(G) ∈ {4, 5, 6, 7}.

In this paper we show that the independence polynomial of any well-covered spider is unimodal and locate its mode, where a spider is a tree having at most one vertex of degree at least three. In addition, we extend some graph transformations, first introduced in [14], respecting independence polynomials. They allow us to reduce several types of well-covered trees to claw-free graphs, and, consequently, to prove that their independence polynomials are unimodal.

In this paper we consider a variation of the Art Gallery Problem. A set of points \( \mathcal{G} \) in a polygon P _n is a connected guard set for P _n provided that is a guard set and the visibility graph of the set of guards \( \mathcal{G} \) in P _n is connected. We use a coloring argument to prove that the minimum number of connected guards which are necessary to watch any polygon with n sides is ⌊n − 2)/2⌋. This result was originally established by induction by Hernández-Peñalver [3]. From this result it easily follows that if the art gallery is orthogonal (each interior angle is 90° or 270°), then the minimum number of connected guards is n/2 − 2.

Quantified Linear Programming is the problem of checking whether a polyhedron specified by a linear system of inequalities is nonempty, with respect to a specified quantifier string. Quantified Linear Programming subsumes traditional Linear Programming, since in traditional Linear Programming, all the program variables are existentially quantified (implicitly), whereas, in Quantified Linear Programming, a program variable may be existentially quantified or universally quantified over a continuous range. On account of the alternation of quantifiers in the specification of a Quantified Linear Program (QLP), this problem is non-trivial.

We present an exact and efficient branch-and-bound algorithm for finding a maximum clique in an arbitrary graph. The algorithm is not specialized for any particular kind of graph. It employs approximate coloring and appropriate sorting of vertices to get an upper bound on the size of a maximum clique. We demonstrate by computational experiments on random graphs with up to 15,000 vertices and on DIMACS benchmark graphs that our algorithm remarkably outperforms other existing algorithms in general. It has been successfully applied to interesting problems in bioinformatics, image processing, the design of quantum circuits, and the design of DNA and RNA sequences for bio-molecular computation.

Let h : ℕ → ℚ be a computable function. A real number x is h-monotonically computable if there is a computable sequence (x _s) of rational numbers which converges to x in such a way that the ratios of the approximation errors are bounded by the function h. In this paper we discuss the h-monotonic computability of semi-computable real numbers, i.e., limits of monotone computable sequences of rational numbers. Especially, we show a sufficient and necessary condition for the function h such that the h-monotonic computability is simply equivalent to the normal computability.