Consider the problem of computing a stabber for polygonal objects. Given a set of objects \({S}\), an object that intersects with all of them is called the stabber of \({S}\). Polynomial time algorithms for constructing a line segment stabber for polygonal objects, if one exists, have been reported in the literature. We introduce the problem of stabbing polygonal objects by monotone chains. We show that a monotone chain that stabs the maximum number of given obstacles can be computed in \(O(n^2 \log n)\) time. We also prove that the maximum number of monotone chains required to stab all polygons can be computed in \(O(n^{2.5})\) time. The main tool used in developing both results is the construction of a directed acyclic graph induced by polygonal objects in a given direction. These results have applications for planning collision-free disjoint paths for several mobile robots in a manufacturing environment.

A secret sharing scheme protects a secret (key) by distributing related information among a group of participants. This is done in such a way that only certain pre-specified groups of these participants (the access structure) can reconstruct the secret. In this paper, we introduce a new measure of the efficiency of a perfect secret sharing scheme and examine methods of producing new secret sharing schemes from existing ones. These constructions can be used to help determine the optimal information rates for certain access structures.

In this paper, we prove that \(3\)-connected projective graphs with minimum valency \(5\) are edge reconstructible.

A set of blocks which is a subset of a unique \(t\)-\((v,k,\lambda_t)\) design is called a \({defining \; set}\) of that design. Using known results, an algorithm for finding smallest defining sets of any \(t\)-\((v,k,\lambda_t)\) design is described. Then the results of this algorithm as applied to the two \(2\)-\((13,3,1)\) designs are given.

The support of a \(t\)-design is the set of all distinct blocks of the design. The support size of a design is denoted by \(b^*\). In this paper, except for \(b^* = 23\), we completely determine the spectrum of support sizes of the case \(v = 10\), \(k = 5\), and \(t = 2\).

The problem of task allocation in distributed systems has been studied by many researchers. Several approaches have been used to model and study the problem, including integer programming, heuristic methods, and graph theoretic models. These approaches considered only restricted forms of the general problem. In this paper, we introduce a new model to represent the problem of allocating tasks on heterogeneous distributed systems. The model consists of a complete split graph that represents the communication cost among tasks as well as the execution cost of each task on the system processors. This model allows the incorporation of various constraints into the allocation problem. We show that the task allocation problem is equivalent to the problem of weighted clique partitioning in complete split graphs, which we proved to be NP-complete. We present a clique partitioning algorithm that employs the properties of split graphs for solving the problem in its general form. We show that the algorithm generates optimal solutions in some cases, while performing fairly well in general.

This paper discusses new Erdös-Gallai type necessary conditions for a sequence \(\prod\) of integers to be \(3\)-hypergraphic. Further, we show that some of the known necessary conditions for \(3\)-hypergraphic sequences are not sufficient.