205481590
Fast and simple algorithms to count the number of vertex covers in an interval graph
This study provides the following fast and simple algorithms for an interval graph: (1) an algorithm for counting the number of vertex covers, and (2) an algorithm for counting the number of minimal vertex covers.
50312
The distributed program reliability analysis on ring-type topologies
Abstract Distributed computing system (DCS) has become very popular for its high fault-tolerance, potential for parallel processing, and better reliability performance. One of the important issues in the design of the DCS is the reliability performance. Distributed program reliability (DPR) is addressed to obtain this reliability measure. In this paper, we propose a polynomial-time algorithm for computing the DPR of ring topology and show that solving the DPR problem on a ring of trees topology is NP-hard. Scope and purpose The widespread use of distributed computing system is due to the price–performance revolution in microelectronics, the development of cost-effective and efficient communication subsets, the development of resource sharing software, and the increased user demands for communication, economical sharing of resources, and productivity. This article is concerned with the analysis of distributed program reliability on a ring-distributed computing system. The distributed program reliability is a useful measure for reliability evaluation of distributed computing system. The distributed program reliability analyses also give a good index for designing a high-reliability-performance-distributed computing system.
5909240
The Computational Complexity of the Reliability Problem on Distributed Systems
Abstract The reliability of a distributed program in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to communicate with other processing elements for remote data files will be executed successfully. This reliability varies according to 1. (1) the topology of the distributed computing system 2. (2) the reliability of the communication links 3. (3) the data files and program distribution among processing elements and 4. (4) the data files required to execute a program. This paper shows that solving this reliability problem is NP-hard even when the distributed computing system is restricted to a series-parallel, a 2-tree, a tree, or a star structure.
45057698
The distributed program reliability analysis on star topologies
Abstract A distributed computing system consists of processing elements, communication links, memory units, data files, and programs. These resources are interconnected via a communication network and controlled by a distributed operating system. The distributed program reliability in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to retrieve data files from other processing elements will be executed successfully. This reliability varies according to (1) the topology of the distributed computing system, (2) the reliability of the communication edges, (3) the data files and programs distribution among processing elements, and (4) the data files required to execute a program. In this paper, we show that computing the distributed program reliability on the star distributed computing systems is NP-hard. We also develop an efficiently solvable case to compute distributed program reliability when some additional file distribution is restricted on the star topology. Scope and purpose Recent advances in VLSI circuitry have a tremendous impact on the price-performance revolution in microelectronics. This development has led to an increased use of workstations connected in the form of a powerful distributed computing system. Potential benefits offered by such distributed computing systems include better cost performance, enhanced fault tolerance, increased system throughput, and efficient sharing of resources. Distributed program reliability is an important measure that should be examined for designing a high fault-tolerance distributed computing system. This reliability varies according to (1) the topology of the distributed computing system, (2) the reliability of the communication edges, (3) the data files and programs distribution among processing elements, and (4) the data files required to execute a program. This article is concerned with the analysis of distributed program reliability on star distributed computing systems.
24905908
Constant Weight Codes for Correcting Symmetric Errors and Detecting Unidirectional Errors
Proposes two classes of constant weight codes, which can be used for correcting t symmetric errors and simultaneously detecting all unidirectional errors. Codes in the first class are in quasi-systematic form and codes in the second class are in systematic form. Since each codeword of codes in both classes can be divided into a data part and a parity check part, the proposed codes have the merit of easily mapping messages into codewords. >
2903221
Algorithms for clique-independent sets on subclasses of circular-arc graphs
A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a 3K2-free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n2). These algorithms suppose that an HCA model of the graph is given.
5671330
Physically based animation and rendering of lightning
We present a physically-based method for animating and rendering lightning and other electric arcs. For the simulation, we present the dielectric breakdown model, an elegant formulation of electrical pattern formation. We then extend the model to animate a sustained, 'dancing' electrical arc, by using a simplified Helmholtz equation for propagating electromagnetic waves. For rendering, we use a convolution kernel to produce results competitive with Monte Carlo ray tracing. Lastly, we present user parameters for manipulation of the simulation patterns.
28156768
A VLSI implementation of the blowfish encryption/decryption algorithm
We propose an efficient hardware architecture for the Blowfish algorithm [1]. The speed is up to 4 bit/clock, which is 9 times faster than a Pentium. By applying operator-rescheduling method, the critical path delay is improved by 21.7%. We have successfully implemented it using Compass cell library targeted at a 0.6 μm TSMC SPTM CMOS process. The die size is 5.7x6.1 mm and the maximum frequency is 50MHz.
1464155
Fast and reliable collision culling using graphics hardware
We present a reliable culling algorithm that enables fast and accurate collision detection between triangulated models in a complex environment. Our algorithm performs fast visibility queries on the GPUs for eliminating a subset of primitives that are not in close proximity. In order to overcome the accuracy problems caused by the limited viewport resolution, we compute the Minkowski sum of each primitive with a sphere and perform reliable 2.5D overlap tests between the primitives. We are able to achieve more effective collision culling as compared to prior object-space culling algorithms. We integrate our culling algorithm with CULLIDE and use it to perform reliable GPU-based collision queries at interactive rates on all types of models, including nonmanifold geometry, deformable models, and breaking objects.