In overloaded task systems, it is by definition not possible to complete all tasks by their deadlines. However, it may still be desirable to maximize the number of in-time task completions. The performance of on-line schedulers with respect to this metric is investigated here. It is shown that in general, an on-line algorithm may perform arbitrarily poorly as compared to clairvoyant (off-line) schedulers. This result holds for general task workloads where there are no constraints on task characteristics. For a variety of constrained workloads that are representative of many practical applications, however, on-line schedulers that do provide a guaranteed level of performance are presented.

We present a new algorithm for computer searches for orthogonal designs. Then we use this algorithm to find new sets of sequences with entries from \(\{0,\pm a, \pm b, \pm c,\pm d\}\) on the commuting variables \(a, b, c, d\) with zero autocorrelation function.

Consider the hit polynomial of the path \(P_{2n}\) embedded in the complete graph \(K_{2n}\). We give a combinatorial interpretation of the \(n\)-th Bessel polynomial in terms of a modification of this hit polynomial, called the ordered hit polynomial. Also, the first derivative of the \(n\)-th Bessel polynomial is shown to be the ordered hit polynomial of \(P_{2n-1}\) embedded in \(K_{2n}\).

In a packer-spoiler game on a graph, two players jointly construct a maximal partial \(F\)-packing of the graph according to some rules, where \(F\) is some given graph. The packer wins if all the edges are used up and the spoiler wins otherwise. The question of which graphs are wins for which player generalizes the questions of which graphs are \(F\)-packable and which are randomly \(F\)-packable. While in general such games are NP-hard to solve, we provide partial results for \(F = P_3\) and solutions for \(F = 2K_2\).

Let G be a \((p,q)\)-graph with p vertices and q edges. An edge-labeling assignment \(\text{L : E} \to \text{N}\) is a map which assigns a positive integer to each edge in E. The induced map \(\text{L}^+ : \text{V} \to \text{N}\) defined by \(\text{L}^+\text{(v)} = \Sigma\{\text{L(u,v) : for all (u,v) in E}\}\) is called the vertex sum. The edge labeling assignment is called \underline{magic} if \(\text{L}^+\) is a constant map. If L is a bijection with \(\text{L(E)} = \{1,2,\ldots,\text{q}\}\) and L is magic then we say L is supermagic. B. M. Stewart showed that \(\text{K}_5\) is not supermagic and when \(\text{n} \equiv 0 \pmod{4}\) , \(\text{K}_\text{n}\) is not supermagic. In this paper, we exhibit supermagicness for a class of regular complete k-partite graphs.

In this paper, we investigate the total colorings of the join graph \(G_1 + G_2\) where \(G_1 \cup G_2\) is a graph with maximum degree at most \(2\). As a consequence of the main result, we prove that if \(G = (2l+1)C_m + (2l+1)C_n\), then \(G\) is Type 2 if and only if \(m = n\) and \(n\) is odd, where \((2l+1)C_m\) and \((2l+1)C_n\) represent \((2l+1)\) disjoint copies of \(C_m\) and \(C_n\), respectively.

In this paper, the standard basis for trades is used to develop an algorithm to classify all simple \(2-(8,3)\) trades. The existence of a total number of \(15,011\) trades reveals the rich structure of trades in spite of a small number of points. Some results on simple \(2-(9, 3)\) trades are also obtained.

We describe an algorithm for finding smallest defining sets of designs. Using this algorithm, we show that the 104 \(STS(19)\) which have automorphism group order at least 9 have smallest defining set sizes in the range 18-23. The numbers of designs with smallest defining sets of \(18, 19, 20, 21, 22\) and \(23\) blocks are, respectively, \(1, 2, 17, 68, 14\) and \(2\).

In this paper, three simple algorithms for the satisfiability problem are presented with their probabilistic analyses. One algorithm, called counting, is designed to enumerate all the solutions of an instance of satisfiability. The second one, namely E-SAT, is proposed for solving the corresponding decision problem. Both the enumeration and decision algorithms have a linear space complexity and a polynomial average time performance for a specified class of instances. The third algorithm is a randomized variant of E-SAT. Its probabilistic analysis yields a polynomial average time performance.

For any abelian group \*A\), we call a graph \(G = (V, E)\) as A-magic if there exists a labeling I: E(G) \(\to \text{A} – \{0\}\) such that the induced vertex set labeling \(I^+: V(G) \to A\)
\[\text{I}^+\text{(v)} = \Sigma \{ \text{I(u,v) : (u,v) in E(G)} \}\]
is a constant map. We denote the set of all \(A\) such that G is \(A\)-magic by \(AM(G)\) and call it as group-magic index set of \(G\).