 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 3 no. 4
1. A note on domino treewidth
In [DO95], Ding and Oporowski proved that for every k, and d, there exists a constant c_k,d, such that every graph with treewidth at most k and maximum degree at most d has domino treewidth at most c_k,d. This note gives a new simple proof of this fact, with a better bound for c_k,d, namely (9k+7)d(d+1) -1. It is also shown that a lower bound of Ω (kd) holds: there are graphs with domino treewidth at least 1/12 × kd-1, treewidth at most k, and maximum degree at most d, for many values k and d. The domino treewidth of a tree is at most its maximum degree.
2. Permutations Containing and Avoiding $\textit{123}$ and $\textit{132}$ Patterns
We prove that the number of permutations which avoid 132-patterns and have exactly one 123-pattern, equals $(n-2)2^{n-3}$, for $n \ge 3$. We then give a bijection onto the set of permutations which avoid 123-patterns and have exactly one 132-pattern. Finally, we show that the number of permutations which contain exactly one 123-pattern and exactly one 132-pattern is $(n-3)(n-4)2^{n-5}$, for $n \ge 5$.
3. Analysis of an Approximation Algorithm for Scheduling Independent Parallel Tasks
In this paper, we consider the problem of scheduling independent parallel tasks in parallel systems with identical processors. The problem is NP-hard, since it includes the bin packing problem as a special case when all tasks have unit execution time. We propose and analyze a simple approximation algorithm called H_m, where m is a positive integer. Algorithm H_m has a moderate asymptotic worst-case performance ratio in the range [4/3 ... 31/18] for all m≥ 6; but the algorithm has a small asymptotic worst-case performance ratio in the range [1+1/(r+1)..1+1/r], when task sizes do not exceed 1/r of the total available processors, where r>1 is an integer. Furthermore, we show that if the task sizes are independent, identically distributed (i.i.d.) uniform random variables, and task execution times are i.i.d. random variables with finite mean and variance, then the average-case performance ratio of algorithm H_m is no larger than 1.2898680..., and for an exponential distribution of task sizes, it does not exceed 1.2898305.... As demonstrated by our analytical as well as numerical results, the average-case performance ratio improves significantly when tasks request for smaller numbers of processors.
4. Classes of graphs with restricted interval models
We introduce q-proper interval graphs as interval graphs with interval models in which no interval is properly contained in more than q other intervals, and also provide a forbidden induced subgraph characterization of this class of graphs. We initiate a graph-theoretic study of subgraphs of q-proper interval graphs with maximum clique size k+1 and give an equivalent characterization of these graphs by restricted path-decomposition. By allowing the parameter q to vary from 0 to k, we obtain a nested hierarchy of graph families, from graphs of bandwidth at most k to graphs of pathwidth at most k. Allowing both parameters to vary, we have an infinite lattice of graph classes ordered by containment.
5. A characterization for all interval doubling schemes of the lattice of permutations
The lattice \textbfS_n of all permutations on a n-element set has been shown to be \emphbounded [CAS], which is a strong constructive property characterized by the fact that \textbfS_n admits what we call an \emph interval doubling scheme. In this paper we characterize all interval doubling schemes of the lattice \textbfS_n, a result that gives a nice precision on the bounded nature of the lattice of permutations. This theorem is a direct corollary of two strong properties that are also given with their proofs.
6. Accelerated series for universal constants, by the WZ method
In this paper, the author presents a method, based on WZ theory, for finding rapidly converging series for universal constants. This method is analogous but different from Amdeberhan and Zeilberger's method.
7. Polytypic Functions Over Nested Datatypes
The theory and practice of polytypic programming is intimately connected with the initial algebra semantics of datatypes. This is both a blessing and a curse. It is a blessing because the underlying theory is beautiful and well developed. It is a curse because the initial algebra semantics is restricted to so-called regular datatypes. Recent work by R. Bird and L. Meertens [3] on the semantics of non-regular or nested datatypes suggests that an extension to general datatypes is not entirely straightforward. Here we propose an alternative that extends polytypism to arbitrary datatypes, including nested datatypes and mutually recursive datatypes. The central idea is to use rational trees over a suitable set of functor symbols as type arguments for polytypic functions. Besides covering a wider range of types the approach is also simpler and technically less involving than previous ones. We present several examples of polytypic functions, among others polytypic reduction and polytypic equality. The presentation assumes some background in functional and in polytypic programming. A basic knowledge of monads is required for some of the examples.