Physical Sciences and Mathematics Commons^™

Kinematic Synthesis Of Deployable-Foldable Truss Structures Using Graph Theory, Dirk B. Warnaar

Mechanical & Aerospace Engineering Theses & Dissertations

A graph theoretic approach is applied to the conceptual design of deployable truss structures. The characteristics that relate to the inter-connectivity of the elements of a deployable truss structure can be captured in a schematic representation, called a graph. A procedure is presented that enables the exhaustive generation of these graphs for structures of any given number of nodes and links and which are foldable onto a plane or onto a line.

A special type of truss structures, called truss modules, is presented. Graphs of this class of structures form a subset of the graphs of truss structures. Two procedures …

On A Unique Tree Representation For P4-Extendible Graphs, B. Jamison, S. Olariu

Computer Science Faculty Publications

Several practical applications in computer science and computational linguistics suggest the study of graphs that are unlikely to have more than a few induced paths of length three. These applications have motivated the notion of a cograph, defined by the very strong restriction that no vertex may belong to an induced path of length three. The class of P₄-extendible graphs that we introduce in this paper relaxes this restriction, and in fact properly contains the class of cographs, while still featuring the remarkable property of admitting a unique tree representation. Just as in the case of cographs, the …

A Mergeable Double-Ended Priority Queue, S. Olariu, Z. Wen

Computer Science Faculty Publications

An implementation of a double-ended priority queue is discussed. This data structure referred to as min–max–pair heap can be built in linear time; the operations Delete-min, Delete-max and Insert take O(log n) time, while Find-min and Find-max run in O(1) time. In contrast to the min-max heaps, it is shown that two min–max–pair heaps can be merged in sublinear time. More precisely, two min–max–pair heaps of sizes n and k can be merged in time O(log (n/k) * log k).

Some Aspects Of The Semi-Perfect Elimination, Stephan Olariu

Computer Science Faculty Publications

Several efficient algorithms have been proposed to construct a perfect elimination ordering of the vertices of a chordal graph. We study the behaviour of two of these algorithms in relation to a new concept, namely the semi-perfect elimination ordering, which provides a natural generalization of chordal graphs.

Estimation In A Marked Poisson Error Recapture Model Of Software Reliability, Rajan Gupta

Mathematics & Statistics Theses & Dissertations

Nayak's (1988) model for the detection, removal, and recapture of the errors in a computer program is extended to a larger family of models in which the probabilities that the successive programs produce errors are described by the tail probabilities of discrete distribution on the positive integers. Confidence limits are derived for the probability that the final program produces errors. A comparison of the asymptotic variances of parameter estimates given by the error recapture and by the repetitive-run procedure of Nagel, Scholz, and Skrivan (1982) is made to determine which of these procedures efficiently uses the test time.

Integration Of Abductive And Deductive Inference Diagnosis Model And Its Application In Intelligent Tutoring System, Jingying Zhang

Computer Science Theses & Dissertations

This dissertation presents a diagnosis model, Integration of Abductive and Deductive Inference diagnosis model (IADI), in the light of the cognitive processes of human diagnosticians. In contrast with other diagnosis models, that are based on enumerating, tracking and classifying approaches, the IADI diagnosis model relies on different inferences to solve the diagnosis problems. Studies on a human diagnosticians' process show that a diagnosis process actually is a hypothesizing process followed by a verification process. The IADI diagnosis model integrates abduction and deduction to simulate these processes. The abductive inference captures the plausible features of this hypothesizing process while the deductive …

A Root Finding Algorithm For Parallel Architecture Machines, Stuti Moitra

Computer Science Theses & Dissertations

In this thesis a parallel algorithm for determining the zeros of any given analytic function is described. Parallelism is achieved by modifying the traditional bisection algorithm for architecture machines.

Given any user supplied function f(X), continuous on the interval A_o ≤ x ≤ B₀, and the tolerance of accuracy an algorithm of determining up to ten roots, with error of approximation less than or equal to tolerance, on parallel systems like Distributed Array Processor (OAP) and N-cube is considered.

A variation of the bisection method has been adapted for this purpose. At each level of iteration a …

Wings And Perfect Graphs, Stephan Olariu

Computer Science Faculty Publications

An edge uv of a graph G is called a wing if there exists a chordless path with vertices u, v, x, y and edges uv, vx, xy. The wing-graph W(G) of a graph G is a graph having the same vertex set as G; uv is an edge in W(G) if and only if uv is a wing in G. A graph G is saturated if G is isomorphic to W(G). A star-cutset in a graph G is a non-empty set of …

Pipelining Data Compression Algorithms, R. L. Bailey, R. Mukkamala

Computer Science Faculty Publications

Many different data compression techniques currently exist. Each has its own advantages and disadvantages. Combining (pipelining) multiple data compression techniques could achieve better compression rates than is possible with either technique individually. This paper proposes a pipelining technique and investigates the characteristics of two example pipelining algorithms. Their performance is compared with other well-known compression techniques.

Efficient Schemes To Evaluate Transaction Performance In Distributed Database Systems, R. Mukkamala, S. C. Bruell

Computer Science Faculty Publications

Database designers and researchers often need efficient schemes to evaluate transaction performance. In this paper, we chose two important performance measures: the average number of nodes accessed and the average number of data items accessed per node by a transaction in a distributed database system. We derive analytical expressions to evaluate these metrics. For general applicability, we consider partially replicated distributed database systems. Our first set of analytic results are closed-form expressions for these two measures. These are based on some fairly restrictive simplifying assumptions. When these assumptions are relaxed, no closed-form expressions exist for these averages. Hence, we develop …

Performance Improvements For Fddi And Csma/Cd Protocols, David Earl Game

Computer Science Theses & Dissertations

The High-Performance Computing Initiative from the White House Office of Science and Technology Policy has defined 20 major challenges in science and engineering which are dependent on the solutions to a number of high-performance computing problems. One of the major areas of focus of this initiative is the development of gigabit rate networks to be used in environments such as the space station or a National Research and Educational Network (NREN).

The strategy here is to use existing network designs as building blocks for achieving higher rates, with the ultimate goal being a gigabit rate network. Two strategies which contribute …

Software Reliability Models, Syed Afzal Hossain

Mathematics & Statistics Theses & Dissertations

The problem considered here is the building of Non-homogeneous Poisson Process (NHPP) model. Currently existing popular NHPP process models like Goel-Okumoto (G-O) and Yamada et al models suffer from the drawback that the probability density function of the inter-failure times is an improper density function. This is because the event no failure in (0, oo] is allowed in these models. In real life situations we cannot draw sample(s) from such a population and also none of the moments of inter-failure times exist. Therefore, these models are unsuitable for modelling real software error data. On the other hand if the density …

On The Unique Tree Representation Of Graphs, Beverly Jamison

Computer Science Theses & Dissertations

This dissertation investigates classes of graphs which admit tree representations unique up to isomorphism. The definitions of these classes are based on local properties of P₄'s, A template structure theorem is given which illustrates the nature of the local properties. The template theorem is instantiated for three different classes of graphs. Properties specific to each of the classes are used to produce a tree representation which can be used for graph computations, such as efficient resolution of graph isomorphism. Linear time algorithms for the recognition of three classes of graphs and for the construction of their tree representations …

A Classification Approach For Automated Reasoning Systems--A Case Study In Graph Theory, Rong Lin

Computer Science Theses & Dissertations

Reasoning systems which create classifications of structured objects face the problem of how object descriptions can be used to reflect their components as well as relations among these components. Current reasoning systems on graph theory do not adequately provide models to discover complex relations among mathematical concepts (eg: relations involving subgraphs) mainly due to the inability to solve this problem. This thesis presents an approach to construct a knowledge-based system, GC (Graph Classification), which overcomes this difficulty in performing automated reasoning in graph theory. We describe graph concepts based on an attribute called Linear Recursive Constructivity (LRC). LRC defines classes …

Performance Modeling And Enhancement For The Atamm Data Flow Architecture, Sukhamoy Som

Electrical & Computer Engineering Theses & Dissertations

Algorithm To Architecture Mapping Model (ATAMM) is a new marked graph model from which the rules for data and control flow in a homogeneous, multicomputer, data flow architecture may be defined. This research is concerned with performance modeling and performance enhancement for periodic execution of large-grain, decision-free algorithms in such an ATAMM defined architecture. Performance measures and bounds are established. Algorithm transformation techniques are identified for performance enhancement and reduction of computing element requirements. Operating strategies are developed for optimum time performance and for sub-optimum time performance under limited availability of computing elements. An ATAMM simulator is used to test …

A New Conjecture About Minimal Imperfect Graphs, H. Meyniel, Stephan Olariu

Computer Science Faculty Publications

H. Meyniel proved that in every minimal imperfect graph, every pair of vertices is joined by a chordless path containing an odd number of edges. We conjectured that in every minimal imperfect graph, every pair of vertices is joined by a path containing an even number of edges. We give an equivalent version of this new conjecture.

The Strong Perfect Graph Conjecture For Pan-Free Graphs, Stephan Olariu

Computer Science Faculty Publications

A graph G is perfect if for every induced subgraph F of G, the chromatic number χ(F) equals the largest number ω(F) of pairwise adjacent vertices in F. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement G contains an odd chordless cycle of length at least five. Its resolution has eluded researchers for more than twenty years. We prove that the conjecture is true for a class of graphs which strictly contains the claw-free graphs.

Weak Bipolarizable Graphs, Stephan Olariu

Computer Science Faculty Publications

We characterize a new class of perfectly orderable graphs and give a polynomial-time recognition algorithm, together with linear-time optimization algorithms for this class of graphs.

No Antitwins In Minimal Imperfect Graphs, Stephan Olariu

Computer Science Faculty Publications

It is customary to call vertices x and y twins if every vertex distinct from x and y is adjacent either to both of them or to neither of them. By analogy, we shall call vertices x and yantitwins if every vertex distinct from x and y is adjacent to precisely one of them. Lovász proved that no minimal imperfect graph has twins. The purpose of this note is to prove the analogous statement for antitwins.

Generic Specifications In Lil And In Ada Via Analogies, George Chester Harrison

Computer Science Theses & Dissertations

We address the problem of .making verifiable specifications in generic program units in the Ada Programming Language*. We illustrate the methodologies of LIL proposed by Joseph Goguen and Justify the use of such a specification languages using analogy programming originally proposed by Nachum Dershowitz. The work in these areas is new and noticeably incomplete. We address our concern about the reusability of Ada software in a programming environment that includes a specification language like LIL. * Ada is a registered trademark of the U.S. Government (Ada Joint Program Office)

Development Of An On-Line Computer System For Cyclic Voltammetry Studies, Tai-Lee Leo Huo

Chemistry & Biochemistry Theses & Dissertations

An Apple II Plus microcomputer was interfaced to a PAR 174A Polarographic Analyser, an HP 7O4OA X-Y recorder and a three-electrode system. This on-line computer system was applied to Cyclic Voltammetry (CV) studies. The interfacing involved both hardware and software development. Various hardware components were used to amplify and transmit the analog signal both going into the computer and coming from the computer. Software programs were written for staircase waveform generation, data acquisition, and plotting the voltammograms obtained.

A package was designed for CV experiments to be used by the students in the instrumental analysis laboratory. This package contains several …

An Algorithm For The Electromagnetic Scattering Due To An Axially Symmetric Body With An Impedance Boundary Condition, F. Stenger, M. Hagmann, J. Scheing

Computer Science Faculty Publications

Let B be a body in R³, and let S denote the boundary of B. The surface S is described by S = {(x, y, z): (x² + Y²)^½= ƒ(z), -1≤ z ≤ I}, where ƒ analytic function that is real and positive on (-1, 1) and ƒ(±1) = 0. An algorithm is described for computing the scattered field due to a plane wave incident field, under Leontovich boundary conditions. The Galerkin method of solution used here leads to a block diagonal matrix involving 2M …