Theoretical Computer Science

We consider a problem of scheduling resumable deteriorating jobs on a single machine with non-availability constraints. The objective is to minimize the total completion time. We prove that the problem with a single non-availability period is NP-hard in ...

The general Bandpass problem is NP-hard and was claimed to be NP-hard when the number of columns is three. Previously we designed a polynomial time row-stacking algorithm for the three column case, to produce a solution that is at most 1 less than the ...

When G is an arbitrary group and V is a finite-dimensional vector space, it is known that every bijective linear cellular automaton @t:V^G->V^G is reversible and that the image of every linear cellular automaton @t:V^G->V^G is closed in V^G for the ...

A tiling in a finite abelian group H is a pair (T,L) of subsets of H such that any h@?H can be uniquely represented as t+l where t@?T and l@?L. This paper studies a finite analogue of self-affine tilings in Euclidean spaces and applies it to a problem ...

We introduce the notion of a T-path within Petri nets, and propose to adopt the model of directed hypergraphs in order to determine properties of nets; in particular, we study the relationships between T-paths and firable sequences of transitions. Let ...

We consider the so called Magnus-Derek game, which is a two-person game played on a round table with n positions. The two players are called Magnus and Derek. Initially there is a token placed at position 0. In each round Magnus chooses a positive ...

We consider the complexity of the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. The problem was supposed to be computationally hard ever since its proposal in 2001. Recently, the first NP-completeness ...

This paper presents a fixed-parameter algorithm for the tree edit distance problem for unordered trees under the unit cost model that works in O(2.62^k@?poly(n)) time and O(n^2) space, where the parameter k is the maximum bound of the edit distance and ...

In this paper the minimum spanning tree problem with uncertain edge costs is discussed. In order to model the uncertainty a discrete scenario set is specified and a robust framework is adopted to choose a solution. The min-max, min-max regret and 2-...

Matching geometric objects with respect to their Hausdorff distance is a well investigated problem in computational geometry with various application areas. The variant investigated in this paper is motivated by the problem of determining a matching (in ...

A cop-robber guarding game is played by the robber-player and the cop-player on a graph G with a partition R and C of the vertex set. The robber-player starts the game by placing a robber (her pawn) on a vertex in R, followed by the cop-player who ...

We introduce networks with additive losses and gains on the arcs. If a positive flow of x units enters an arc a, then x+g(a) units exit. Arcs may increase or consume flow, i.e., they are gainy or lossy. Such networks have various applications, e.g., in ...

Initially stated in terms of Beatty sequences, the Fraenkel conjecture can be reformulated as follows: for a k-letter alphabet A, with a fixed k>=3, there exists a unique balanced infinite word, up to letter permutations and shifts, that has mutually ...

We propose an improved algorithm for counting the number of Hamiltonian cycles in a directed graph. The basic idea of the method is sequential acceptance/rejection, which is successfully used in approximating the number of perfect matchings in dense ...

In a balloon drawing of a tree, all the children under the same parent are placed on the circumference of the circle centered at their parent, and the radius of the circle centered at each node along any path from the root reflects the number of ...

The Myhill-Nerode Theorem states that the equivalence relation ~"L given by a language L has finite index if and only if L is accepted by a finite automaton. In this paper we give several generalizations of the theorem which are algebraic in nature. In ...

Parallel communicating grammar systems with regular control (RPCGS, for short) are introduced, which are obtained from returning regular parallel communicating grammar systems by restricting the derivations that are executed in parallel by the various ...

A resource-bounded version of the statement ''no algorithm recognizes all non-halting Turing machines'' is equivalent to an infinitely often (i.o.) superpolynomial speedup for the time required to accept any (paddable) coNP-complete language and also ...

C. Calude, A. Nies, L. Staiger, and F. Stephan posed the following question about the relation between plain and prefix Kolmogorov complexities (see their paper in DLT 2008 conference proceedings): does the domain of every optimal decompressor contain ...

The Union-Find data structure for maintaining disjoint sets is one of the best known and widespread data structures, in particular the version with constant-time Union and efficient Find. Recently, the question of how to handle deletions from the ...

In this note, we state a conjecture, and prove it in the periodic case, which is an equality relating the number of factors and palindromic factors of infinite words. This equality establishes a link between two inequalities, one due to Droubay, Justin ...