Physical Sciences and Mathematics Commons^™

A Simulated Annealing/Tabu Search Algorithm For The Vehicle Routing Problem, Jeffrey Dale White, Billy E. Gillett

Computer Science Technical Reports

The Vehicle Routing Problem is an NP-complete problem that has been studied extensively since it was introduced in 1958 by G. B. Dantzig and J. H. Ramser. This thesis creates three algorithms that endeavor to find an optimal solution for each problem tested. Two of the algorithms (Simulated Annealing and Tabu Search) have been used previously to solve this problem. These two solution methods are revisited to discover whether a new approach to creating routes will produce the best-known optimal values every time. New routes are created by forming route neighborhoods and then selecting cities from these neighborhoods for insertion. …

Process Driven Software Engineering Environments, John Hayes Lampkin, T. Lo, Daniel C. St. Clair

Computer Science Technical Reports

Software development organizations have begun using Software Engineering Environments (SEEs) with the goal of enhancing the productivity of software developers and improving the quality of software products. The encompassing nature of a SEE means that it is typically very tightly coupled with the way an organization does business. To be most effective, the components of a SEE must be well integrated and the SEE itself must be integrated with the organization.

The challenge of tool integration increases considerably when the components of the environment come from different vendors and support varying degrees of “openness”. The challenge of integration with the …

Subsumption In Modal Logic, Dirk Heydtmann, Ralph W. Wilkerson

Computer Science Technical Reports

Subsumption has long been known as a technique to detect redundant clauses in the search space of automated deduction systems for classical first order logic. In recent years several automated deduction methods for non-classical modal logics have been developed. This thesis explores, how subsumption can be made to work in the context of these modal logic deduction methods.

Many modern modal logic deduction methods follow an indirect approach. They translate the modal sentences into some other target language, and then determine whether there exists a proof in that language, rather than doing deduction in the modal language itself. Consequently, subsumption …

The Difficulty Of Approximating The Chromatic Number For Random Composite Graphs, Jeffrey Wayne Jenness, Billy E. Gillett

Computer Science Technical Reports

Combinatorial Optimization is an important class of techniques for solving Combinatorial Problems. Many practical problems are Combinatorial Problems, such as the Traveling Salesman Problem (TSP) and Composite Graph Coloring Problem (CGCP). Unfortunately, both of these problems are NP-complete and it is not known if efficient algorithms exist to solve these problems. Even approximation with guaranteed results can be just as difficult. Recently, many generalized search techniques have been developed to improve upon the solutions found by the heuristic algorithms.

This paper presents results for CGCP. In particular, exact and heuristic algorithms are presented and analyzed. This study is made, to …

A Syntax-Directed Editor For Borland’S Turbo Pascal, John Gatewood Ham, Thomas J. Sager

Computer Science Technical Reports

This study details the design and implementation of the LSD program, a syntax-directed editor for use in editing the source code for Borland’s Turbo Pascal. LSD is a dual-mode editor which allows both traditional text editing and also grammar-based editing. LSD promotes better programming for novice users by allowing the user to edit the program with a graphical representation of a parse tree. A list of syntactically correct choices is displayed at each point where a choice must be made in the structure of the program. Since only these choices are available, no syntax errors are possible. For more advanced …

Fault-Tolerant Ring Embeddings In Hypercubes -- A Reconfigurable Approach, Jun-Lin Liu, Bruce M. Mcmillin

Computer Science Technical Reports

We investigate the problem of designing reconfigurable embedding schemes for a fixed hypercube (without redundant processors and links). The fundamental idea for these schemes is to embed a basic network on the hypercube without fully utilizing the nodes on the hypercube. The remaining nodes can be used as spares to reconfigure the embeddings in case of faults. The result of this research shows that by carefully embedding the application graphs, the topological properties of the embedding can be preserved under fault conditions, and reconfiguration can be carried out efficiently.

In this dissertation, we choose the ring as the basic network …

Effect Of Joystick Versus Control Yoke Use On Personal Computer (Pc) Flight Training: A Comparative Analysis, Gregory Alan Fontaine

Master's Theses - Daytona Beach

The purpose of this study was to provide a comparative performance analysis of a generic control yoke device and a generic joystick device. The comparison provided data needed for further evaluation of personal computer (PC) aircrew training device (ATD) potential. Both devices were used in support of the same PC flight simulation software program, and were evaluated using the experimental research method. Objective and subjective data were obtained during controlled testing, and subsequently analyzed using basic summation and t-test methods. The results tested the research hypothesis that there is no significant difference in personal computer ATD operator performance using a …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 9, Number 10, December 1993, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A ten page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Parallel H-V Drawings Of Binary Trees, Panagiotis T. Metaxas, Grammati E. Pantziou, Antonis Symvonis

Computer Science Technical Reports

In this paper we present a method to obtain optimal h-v and inclusion drawings in parallel. Based on parallel tree contraction, our method computes optimal (with respect to a class of cost functions of the enclosing rectangle) drawings in $O(\log^2 n)$ parallel time by using a polynomial number of EREW processors. The number of processors reduces substantially when we study minimum area drawings. The method can be extended to compute optimal inclusion layouts in the case where each leaf $l$ of the tree is represented by rectangle $l_x \times l_y$ (the dimensions of which are part of the input). For …

Probing Tcp Implementations, Douglas E. Comer, John C. Lin

Department of Computer Science Technical Reports

No abstract provided.

An Optimal O(Log Log N) Time Parallel Algorithm For Detecting All Squares In A String, Albert Apostolico, Dany Breslauer

Department of Computer Science Technical Reports

No abstract provided.

A Generalized Schwarz Splitting Method Based On Hermite Collocation For Elliptic Boundary Value Problems, Yu-Ling Lai, Apostolos Hadjidimos, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.

Parallel Dynamic Mesh Generation And Domain Decomposition, Poting Wu, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.

Combinatorial Optimization Problems For Which Almost Every Algorithm Is Asymptotically Optimal, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

A Probabilistic Analysis Of A String Editing Problem And Its Variations, Guy Louchard, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

A Scheduling Policy With Maximal Stability Region For Rings Networks With Spatial Reuse, Leonidas Georgiadis, Wojciech Szpankowski, Leondros Tassiulas

Department of Computer Science Technical Reports

No abstract provided.

Extending Multidatabase Transaction Management Techniques To Software Development Environments, Aidong Zhang, Omran Bukhres

Department of Computer Science Technical Reports

No abstract provided.

C3: A Parallel Model For Coarse-Grained Machines, Susanne E. Hambrusch, Ashfaq A. Khokhar

Department of Computer Science Technical Reports

No abstract provided.

A View-Based Approach To Relaxing Global Serializability In Multidatabase Systems, Aidong Zhang, Evaggelia Pitoura, Bharat K. Bhargava

Department of Computer Science Technical Reports

No abstract provided.

Constructing Distributed Schedulers Using The Messiahs Interface Language, Steve J. Chapin, Eugene H. Spafford

Department of Computer Science Technical Reports

No abstract provided.

Data Structures And Algorithms For The String Statistics Problem, Alberto Apostolico, Franco P. Preparata

Department of Computer Science Technical Reports

No abstract provided.

The Use Of Neural Networks To Support "Intelligent" Scientific Computing, Anupam Joshi, Csanjiva Weerawarana, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.

Asymptotic Behavior Of The Lempel-Ziv Parsing Scheme And Digital Search Trees, Philippe Jaquet, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Scheduling Support Mechanisms For Autonomous, Heterogeneous, Distributed Systems (Ph.D. Thesis), Steve J. Chapin

Department of Computer Science Technical Reports

No abstract provided.

Parallel Numerical Methods For Partial Differential Equations (Ph.D. Thesis), Sang-Bae Kim

Department of Computer Science Technical Reports

No abstract provided.

Correctness Proof Of A Geometric Constraint Solver, Ioannis Fudos, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.

Object-Orientation In Multidatabase Systems, Evaggelia Pitoura, Omran Bukhres, Ahmed K. Elmagarmid

Department of Computer Science Technical Reports

No abstract provided.

Collaborative Multimedia Game Environments, Vinod Anupam, Chandrajit L. Bajaj

Department of Computer Science Technical Reports

No abstract provided.

Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh

Computer Science: Faculty Publications and Other Works

We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη + cLηlog P) time, where L is the number of flits in a packet, and η = min {d,L]; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O(log 3 …

A Prototype Architecture For An Automated Scenario Generation System For Combat Simulations, Mark W. Pfefferman

Theses and Dissertations

This research effort examines the problem of automating the scenario generation process and presents a prototype architecture for an automated scenario generation system. This architecture is designed using an object- oriented approach which leads to a modular and modifiable design. The architecture provides a mechanism for automatically generating scenario files from a textual US Army operation order. This translation process occurs in two phases. First, the text operation order is translated into an intermediate format called the mission file. In the second phase, the system reads the mission file, instantiates intelligent entities, and assigns missions to those entities. The intelligent …