International Journal of Foundations of Computer Science

This paper studies the problem of orienting all edges of a weighted graph such that the maximum weighted outdegree of vertices is minimized. This problem, which has applications in the guard arrangement for example, can be shown to be -hard generally. In this paper we first give optimal orientation algorithms which run in polynomial time for the following special cases: (i) the input is an unweighted graph, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a simple, combinatorial, -approximation algorithm for the general case, where w_max and w_min are the maximum and the minimum weights of edges, respectively, and ε is some small positive real number that depends on the input.

We consider the following clustering problems: given an undirected graph, partition its vertices into disjoint clusters such that each cluster forms a clique and the number of edges within the clusters is maximized (Max-ECP), or the number of edges between clusters is minimized (Min-ECP). These problems arise naturally in the DNA clone classification. We investigate the hardness of finding such partitions and provide approximation algorithms. Further, we show that greedy strategies yield constant factor approximations for graph classes for which maximum cliques can be found efficiently.

We present a new method for finding closed forms of recursive Boolean function definitions. Traditionally, these closed forms are found by Kleene iteration: iterative approximation until a fixed point is reached. Conceptually, our new method replaces each k-ary function by 2^k Boolean constants defined by mutual recursion. The introduction of an exponential number of constants is mitigated by the simplicity of their definitions and by the use of a novel variant of ROBDDs to avoid repeated computation. Experiments suggest that this approach is significantly faster than Kleene iteration for examples that require many Kleene iteration steps.

We investigate an online scheduling problem motivated by pull-based data delivery systems where there is a server keeping a number of pages; and clients requesting the same page can be satisfied simultaneously by one broadcast. We focus on the special case where preemption is allowed but aborted requests can never be satisfied again. The HEU algorithm of Woeginger [10] is proven to be optimal in maximizing the number of satisfied requests when the pages have equal length and the requests have tight deadlines. However, we show that when there are maximum bounds on the number and weight of requests at any time in the system, the HEU algorithm is not optimal. We then propose a modified algorithm, VAR, which is optimal for this case.

Some combinatorial generation problems can be broken into subproblems for which loopless algorithms already exist. This article discusses means by which loopless algorithms can be fused to produce a new loopless algorithm that solves the original problem. It demonstrates this method with two new loopless algorithms. The first generates well-formed parenthesis strings containing two different types of parentheses. The second generates multiset permutations in linear space using only arrays; it is simpler and more efficient than the recent algorithm of Korsh & LaFollette.

We show that two data structures, min-augmented range tree and priority search pennant, efficiently support all the required operations for updatable IP router tables and argue that both structures are better suited for the one-dimensional dynamic IP lookup problem than the priority search tree (PST) used in a previous solution. It is possible to maintain both structures in time O(1) after a rotation, while PST with n elements may require Ω(log n) steps for a single rotation. Therefore, the proposed structures can be balanced using a larger class of rebalancing schemes compared to PST. Both structures are also of interest independently of the IP lookup problem and may be used as attractive implementations of priority search queues in other contexts as well.

The maximum subarray problem is to find the array portion that maximizes the sum of array elements in it. For K disjoint maximum subarrays, Ruzzo and Tompa gave an O(n) time solution for one-dimension. This solution is, however, difficult to extend to two-dimensions. While a trivial solution of O(Kn³) time is easily obtainable for a two-dimensional array of size n × n, little study has been undertaken to improve the time complexity. We first propose an O(n + K log K) time solution for one-dimension. This is asymptotically equivalent to Ruzzo and Tompa's when sorted order is needed. Based on this, we achieve O(n³ + Kn²log n) time for two-dimensions. This is cubic time when K ≤ n/log n. We also show that this upper bound does not exceed O(n³log n) for K > n, namely O(n³ + min(K,n) · n log n).

We consider two-machine flow shop problems with exact delays. In this model, there are two machines, the upstream machine and the downstream machine. Each job j has two operations: the first operation has to be processed on the upstream machine and the second operation has to be processed on the downstream machine, subject to the constraint that the time interval between the completion time of the first operation and the start time of the second operation is exactly . We concentrate on the objectives of makespan and total completion time. For the makespan objective, we first show that the problem is strongly NP-hard even if there are only two possible delay values. We then show that some special cases of the problem are solvable in polynomial time. Finally, we design efficient approximation algorithms for the general case and some special cases. For the total completion time objective, we give optimal polynomial-time algorithm for a special case and an efficient approximation algorithm for another one.

Restarting automata were introduced by Jančar et al. to model the so-called analysis by reduction. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even shorter word. Here we consider a natural generalization of this model, called shrinking restarting automaton, where we only require that there exists a weight function such that each rewrite step decreases the weight of the tape content with respect to that function. While it is still unknown whether the two most general types of one-way restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. As a consequence of our proof, it turns out that there exists a reduction by morphisms from the language class to the class . Further, we will see that the shrinking restarting automaton is a rather robust model of computation. Finally, we will relate shrinking RRWW-automata to finite-change automata. This will lead to some new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.

Using the fact that the Parikh matrix mapping is not an injective mapping, the paper investigates some properties of the set of the binary words having the same Parikh matrix; these words are called "amiable" Some results concerning the conditions when the equivalence classes of amiable words have more than one element, a characterization theorem concerning a graph associated to an equivalence class of amiable words, and some basic properties of a rank distance defined on these classes are the main subjects considered here.

The online squarefree recognition problem is to detect the first occurrence of a square in a string whose characters are provided as input one at a time. We present an efficient algorithm to solve this problem for strings over arbitrarily ordered alphabets in O(n log n) time, where n is the ending position of the first square. We also note that the same technique yields an O(n·(|Σ_n|+log n))-time algorithm for general alphabets, where |Σ_n| is the number of different symbols in the first n positions of the input string. (This is faster than the previously fastest method for general alphabets when |Σ_n| = o(log² n).) Finally, we present a simple algorithm for a dynamic version of the problem over general alphabets in which we are initially given a squarefree string, followed by a series of updates, and the objective is to determine after each update if the resulting string is still squarefree.

We characterize the computational power of several restricted variants of communicating P systems. We show that 2-deterministic communicating P systems with 2 membranes, working in either minimally or maximally parallel mode, are computationally universal. Considering the sequential mode, 2 membranes are shown to characterize the power of partially blind multicounter machines. Next, a characterization of the power of 1-deterministic communicating P systems is given. Finally, we show that the nondeterministic variant in maximally parallel mode is universal already with 1 membrane. These results demonstrate differences in computational power between nondeterminism, 2-determinism and 1-determinism, on one hand, and between sequential, minimally and maximally parallel modes, on the other hand.