The greedy algorithm for domination in graphs of maximum degree 3

We show that for a connected graph with n nodes and e edges and maximum degree at most 3, the size of the dominating set found by the greedy algorithm is at most if , if , and if .     

Structural equation modeling with near singular covariance matrices

Conventional structural equation modeling involves fitting a structural model to the sample covariance matrix . Due to collinearity or small samples with practical data, nonconvergences often occur in the estimation process. For a small constant a, this paper proposes to fit the structural model to the covariance matrix . When treating as the sample covariance matrix in the maximum likelihood (ML) procedure, consistent parameter estimates are still obtained. The asymptotic distributions of the parameter estimates and the corresponding likelihood ratio statistic are studied and compared to those by the conventional ML. Two rescaled statistics for the overall model evaluation with modeling are constructed. Empirical results imply that the estimates from modeling are more efficient than those of fitting the structural model to even when data are normally distributed. Simulations and real data examples indicate that modeling allows us to evaluate the overall model structure even when is literally singular. Implications of modeling in a broader context are discussed.     

The 2-dipath chromatic number of Halin graphs

A 2-dipath k-coloring f of an oriented graph is a mapping from to the color set {1,2,…,k} such that f(x)≠f(y) whenever two vertices x and y are linked by a directed path of length 1 or 2. The 2-dipath chromatic number of is the smallest k such that has a 2-dipath k-coloring. In this paper we prove that if is an oriented Halin graph, then . There exist infinitely many oriented Halin graphs such that .     

Generalized penetration depth computation

Penetration depth () is a distance measure that is used to describe the extent of overlap between two intersecting objects. Most of the prior work in computation has been restricted to translational, which is defined as the minimal translational motion that one of the overlapping objects must undergo in order to make the two objects disjoint. In this paper, we extend the notion of to take into account both translational and rotational motion to separate the intersecting objects, namely generalized. When an object undergoes a rigid transformation, some point on the object traces the longest trajectory. The generalized between two overlapping objects is defined as the minimum of the longest trajectories of one object, under all possible rigid transformations to separate the overlapping objects.We present three new results to compute generalized between polyhedral models. First, we show that for two overlapping convex polytopes, the generalized is the same as the translational . Second, when the complement of one of the objects is convex, we pose the generalized computation as a variant of the convex containment problem and compute an upper bound using optimization techniques. Finally, when both of the objects are non-convex, we treat them as a combination of the above two cases and present an algorithm that computes a lower and an upper bound on the generalized . We highlight the performance of our algorithms on different models that undergo rigid motion in the 6-dimensional configuration space. Moreover, we utilize our algorithm for complete motion planning of rigid robots undergoing translational and rotational motion in a plane or in 3D space. In particular, we use generalized computation for performing C-obstacle query and checking path non-existence.     

The formalism underlying EASYMAP: A precompiler for refinement-based exploration of hierarchical data organizations

In the computer science community, data structure design is mainly conducted at a high level of abstraction under the implicit assumption that the platform contains a monolithic memory. Exploiting platform-related knowledge such as available on-chip and off-chip memory sizes, the cache size, and the number of banks is mainly conducted in the system engineering community when the refined data structure has already been chosen. A convergence of both communities is desirable since this can lead to powerful optimizations.To achieve the convergence mentioned above, data-related transformations have been researched extensively in the recent past. Many of these transformations have a direct and large impact on memory footprint, execution time and energy consumption. Unfortunately, however, the most effective transformations are applied manually (e.g. in C code) and these result in a very time-consuming and error-prone design process. To overcome this burden, our general research goal is to develop a computer-aided design tool, called , that helps the designer to correctly construct the C code of an efficient but difficult-to-understand data structure. The formal design of is the topic of this article with the emphasis on , the internal language of . is based on a novel extension of Separation Logic’s spatial conjunction operator (∗), allowing it to concisely describe access operations of an irregularly accessed complex data organization. is the basic building block of ; it serves the purpose of automating ’s refinement process and proving that it is correct by construction.