Physical Sciences and Mathematics Commons^™

A Digital Library For The National Advisory Committee For Aeronautics, Michael L. Nelson

Computer Science Faculty Publications

We describe the digital library (DL) for the National Advisory Committee for Aeronautics (NACA), the NACA Technical Report Server (NACATRS). The predecessor organization for the National Aeronautics and Space Administration (NASA), NACA existed from 1915 until 1958. The primary manifestation of NACA's research was the NACA report series. We describe the process of converting this collection of reports to digital format and making it available on the World Wide Web (WWW) and is a node in the NASA Technical Report Server (NTRS). We describe the current state of the project, the resulting DL technology developed from the project, and the …

Reconfigurable Shift Switching Parallel Comparators, R. Lin, S. Olariu

Computer Science Faculty Publications

We present novel asynchronous VLSI comparator schemes which are based on recently proposed reconfigurable shift switch logic and the traditional (precharged) CMOS domino logic. The schemes always produce a semaphore as a by-product of the process to indicate the end of domino process, which requires no additional delay and a minimal number of additional devices. For a large percentage of inputs the computations are much faster than traditional synchronous comparators due to the full utilization of the inherent speed of the circuits. Also the schemes are simple, area compact and stable.

On The P-Connectedness Of Graphs – A Survey, Luitpold Babel, Stephan Olariu

Computer Science Faculty Publications

A graph is said to be p-connected if for every partition of its vertices into two non-empty, disjoint, sets some chordless path with three edges contains vertices from both sets in the partition. As it turns out, p-connectedness generalizes the usual connectedness of graphs and leads, in a natural way, to a unique tree representation for arbitrary graphs.

This paper reviews old and new results, both structural and algorithmic, about p-connectedness along with applications to various graph decompositions.

On The Structure Of Graphs With Few P4s, Luitpold Babel, Stephan Olariu

Computer Science Faculty Publications

We present new classes of graphs for which the isomorphism problem can be solved in polynomial time. These graphs are characterized by containing — in some local sense — only a small number of induced paths of length three. As it turns out, every such graph has a unique tree representation: the internal nodes correspond to three types of graph operations, while the leaves are basic graphs with a simple structure. The paper extends and generalizes known results about cographs, P₄-reducible graphs, and P₄-sparse graphs.

A Fast Parallel Algorithm To Recognize P4-Sparse Graphs, Rong Lin, Stephan Olariu

Computer Science Faculty Publications

A number of problems in mobile computing, group-based collaboration, automated theorem proving, networking, scheduling, and cluster analysis suggested the study of graphs featuring certain “local density” characteristics. Typically, the notion of local density is equated with the absence of chordless paths of length three or more. Recently, a new metric for local density has been proposed, allowing a number of such induced paths to occur. More precisely, a graphG is called P4-sparse if no set of five vertices inG induces more than one chordless path of length three. P4-sparse graphs generalize the well-known class of cographs corresponding to …

Buckets: Aggregative, Intelligent Agents For Publishing, Michael L. Nelson, Kurt Maly, Stewart N. T. Shen, Mohammad Zubair

Computer Science Faculty Publications

Buckets are an aggregative, intelligent construct for publishing in digital libraries. The goal of research projects is to produce information. This information is often instantiated in several forms, differentiated by semantic types (report, software, video, datasets, etc.). A given semantic type can be further differentiated by syntactic representations as well (PostScript version, PDF version, Word version, etc.). Although the information was created together and subtle relationships can exist between them, different semantic instantiations are generally segregated along currently obsolete media boundaries. Reports are placed in report archives, software might go into a software archive, but most of the data and …

Creating A Canonical Scientific And Technical Information Classification System For Ncstrl+, Melissa E. Tiffany, Michael L. Nelson

Computer Science Faculty Publications

The purpose of this paper is to describe the new subject classification system for the NCSTRL+ project. NCSTRL+ is a canonical digital library (DL) based on the Networked Computer Science Technical Report Library (NCSTRL). The current NCSTRL+ classification system uses the NASA Scientific and Technical (STI) subject classifications, which has a bias towards the aerospace, aeronautics, and engineering disciplines. Examination of other scientific and technical information classification systems showed similar discipline-centric weaknesses. Traditional, library-oriented classification systems represented all disciplines, but were too generalized to serve the needs of a scientific and technically oriented digital library. Lack of a suitable existing …

Time-Optimal Tree Computations On Sparse Meshes, D. Bhagavathi, V. Bokka, H. Gurla, S. Olariu, J. L. Schwing

Computer Science Faculty Publications

The main goal of this work is to fathom the suitability of the mesh with multiple broadcasting architecture (MMB) for some tree-related computations. We view our contribution at two levels: on the one hand, we exhibit time lower bounds for a number of tree-related problems on the MMB. On the other hand, we show that these lower bounds are tight by exhibiting time-optimal tree algorithms on the MMB. Specifically, we show that the task of encoding and/or decoding n-node binary and ordered trees cannot be solved faster than Ω(log n) time even if the MMB has an infinite …

Lyceum: A Multi-Protocol Digital Library Gateway, Ming-Hokng Maa, Michael L. Nelson, Sandra L. Esler

Computer Science Faculty Publications

Lyceum is a prototype scalable query gateway that provides a logically central interface to multi-protocol and physically distributed, digital libraries of scientific and technical information. Lyceum processes queries to multiple syntactically distinct search engines used by various distributed information servers from a single logically central interface without modification of the remote search engines. A working prototype (http://www.larc.nasa.gov/lyceum/) demonstrates the capabilities, potentials, and advantages of this type of meta-search engine by providing access to over 50 servers covering over 20 disciplines.

Time- And Cost-Optimal Parallel Algorithms For The Dominance And Visibility Graphs, D. Bhagavathi, H. Gurla, S. Olariu, J. L. Schwing, J. Zhang

Computer Science Faculty Publications

The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non-overlapping rectangles in the plane. These graphs are intended to capture various visibility relations amongst the rectangles in the collection. The contribution of this paper is to propose time- and cost-optimal algorithms to construct two such graphs, namely, the dominance graph (DG, for short) and the visibility graph (VG, for short). Specifically, we show that with a collection of n non-overlapping rectangles as input, both these structures can be constructed in θ (log n) time using n processors in the CREW model.

An Optimal Path Cover Algorithm For Cographs, R. Lin, S. Olariu

Computer Science Faculty Publications

The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. In this paper, we present an optimal algorithm for determining a minimum path cover for a cograph G. In case G has a Hamiltonian path (cycle) our algorithm exhibits the path (cycle) as well.

A Linear-Time Recognition Algorithm For P4-Reducible Graphs, B. Jamison, S. Olariu

Computer Science Faculty Publications

The P₄-reducible graphs are a natural generalization of the well-known class of cographs, with applications to scheduling, computational semantics, and clustering. More precisely, the P₄-reducible graphs are exactly the graphs none of whose vertices belong to more than one chordless path with three edges. A remarkable property of P₄-reducible graphs is their unique tree representation up to isomorphism. In this paper we present a linear-time algorithm to recognize P₄-reducible graphs and to construct their corresponding tree representation.

Linear Time Optimization Algorithms For P4-Sparse Graphs, Beverly Jamison, Stephan Olariu

Computer Science Faculty Publications

Quite often, real-life applications suggest the study of graphs that feature some local density properties. In particular, graphs that are unlikely to have more than a few chordless paths of length three appear in a number of contexts. A graph G is P₄-sparse if no set of five vertices in G induces more than one chordless path of length three. P₄-sparse graphs generalize both the class of cographs and the class of P₄-reducible graphs. It has been shown that P₄-sparse graphs can be recognized in time linear in the size of the …

Electronic Document Distribution: Design Of The Anonymous Ftp Langley Technical Report Server, Michael L. Nelson, Gretchen L. Gottlich

Computer Science Faculty Publications

An experimental electronic dissemination project, the Langley Technical Report Server (LTRS), has been undertaken to determine the feasibility of delivering Langley technical reports directly to the desktops of researchers worldwide. During the first six months, over 4700 accesses occurred and over 2400 technical reports were distributed. This usage indicates the high level of interest that researchers have in performing literature searches and retrieving technical reports at their desktops. The initial system was developed with existing resources and technology. The reports are stored as files on an inexpensive UNIX workstation and are accessible over the Internet. This project will serve as …

A Greedy Hypercube-Labeling Algorithm, D. Bhagavathi, C. E. Grosch, S. Olariu

Computer Science Faculty Publications

Due to its attractive topological properties, the hypercube multiprocessor has emerged as one of the architectures of choice when it comes to implementing a large number of computational problems. In many such applications, Gray-code labelings of the hypercube are a crucial prerequisite for obtaining efficient algorithms. We propose a greedy algorithm that, given an n-dimensional hypercube H with N=2² nodes, returns a Gray-code labeling of H, that is, a labeling of the nodes with binary strings of length n such that two nodes are neighbors in the hypercube if, and only if, their labels differ in exactly …

The World Wide Web And Technology Transfer At Nasa Langley Research Center, Michael L. Nelson, David J. Bianco

Computer Science Faculty Publications

NASA Langley Research Center (LaRC) began using the World Wide Web (WWW) in the summer of 1993, becoming the first NASA installation to provide a Center-wide home page. This coincided with a reorganization of LaRC to provide a more concentrated focus on technology transfer to both aerospace and non-aerospace industry. Use of the WWW and NCSA Mosaic not only provides automated information dissemination, but also allows for the implementation, evolution and integration of many technology transfer applications. This paper describes several of these innovative applications, including the on-line presentation of the entire Technology Opportunities Showcase (TOPS), an industrial partnering showcase …

World Wide Web Implementation Of The Langley Technical Report Server, Michael L. Nelson, Gretchen L. Gottlich, David J. Bianco

Computer Science Faculty Publications

On January 14, 1993, NASA Langley Research Center (LaRC) made approximately 130 formal, 'unclassified, unlimited' technical reports available via the anonymous FTP Langley Technical Report Server (LTRS). LaRC was the first organization to provide a significant number of aerospace technical reports for open electronic dissemination. LTRS has been successful in its first 18 months of operation, with over 11,000 reports distributed and has helped lay the foundation for electronic document distribution for NASA. The availability of World Wide Web (WWW) technology has revolutionized the Internet-based information community. This paper describes the transition of LTRS from a centralized FTP site to …

A Strategy For Electronic Dissemination Of Nasa Langley Technical Publications, Donna G. Roper, Mary K. Mccaskill, Scott D. Holland, Joanne L. Walsh, Michael L. Nelson, Susan L. Adkins, Manjula Y. Ambur, Bryan A. Campbell

Computer Science Faculty Publications

To demonstrate NASA Langley Research Center's relevance and to transfer technology to external customers in a timely and efficient manner, Langley has formed a working group to study and recommend a course of action for the electronic dissemination of technical reports (EDTR). The working group identified electronic report requirements (e.g., accessibility, file format, search requirements) of customers in U.S. industry through numerous site visits and personal contacts. Internal surveys were also used to determine commonalities in document preparation methods. From these surveys, a set of requirements for an electronic dissemination system was developed. Two candidate systems were identified and evaluated …

Optimal Greedy Algorithms For Indifference Graphs, Peter J. Looges, Stephan Olariu

Computer Science Faculty Publications

A fundamental problem in social sciences and management is understanding and predicting decisions made by individuals, various groups, or the society as a whole. In this context, one important concept is the notion of indifference. We characterize the class of indifference graphs, that is, graphs which arise in the process of quantifying indifference relations. In particular, we show that these graphs are characterized by the existence of a special ordering of their vertices. As it turns out, this ordering leads naturally to optimal greedy algorithms for a number of computational problems, including coloring, finding a shortest path between two vertices, …

Intel Nx To Pvm 3.2 Message Passing Conversion Library, Trey Arthur, Michael L. Nelson

Computer Science Faculty Publications

NASA Langley Research Center has developed a library that allows Intel NX message passing codes to be executed under the more popular and widely supported Parallel Virtual Machine (PVM) message passing library. PVM was developed at Oak Ridge National Labs and has become the defacto standard for message passing. This library will allow the many programs that were developed on the Intel iPSC/860 or Intel Paragon in a Single Program Multiple Data (SPMD) design to be ported to the numerous architectures that PVM (version 3.2) supports. Also, the library adds global operations capability to PVM. A familiarity with Intel NX …

A Comparison Of Queueing, Cluster And Distributed Computing Systems, Joseph A. Kaplan, Michael L. Nelson

Computer Science Faculty Publications

Using workstation clusters for distributed computing has become popular with the proliferation of inexpensive, powerful workstations. Workstation clusters offer both a cost effective alternative to batch processing and an easy entry into parallel computing. However, a number of workstations on a network does not constitute a cluster. Cluster management software is necessary to harness the collective computing power. A variety of cluster management and queuing systems are compared: Distributed Queueing Systems (DQS), Condor, Load Leveler, Load Balancer, Load Sharing Facility (LSF - formerly Utopia), Distributed Job Manager (DJM), Computing in Distributed Networked Environments (CODINE), and NQS/Exec. The systems differ in …

The Morphology Of Convex Polygons, Stephan Olariu

Computer Science Faculty Publications

A simple polygon P is said to be unimodal if for every vertex of P, the Euclidian distance function to the other vertices of P is unimodal. The study of unimodal polygons has emerged as a fruitful area of computational and discrete geometry. We study unimodality properties of a number of special convex polygons from the morphological point of view. In particular, we establish a hierarchy among three classes of convex polygons in terms of their unimodality properties.

A Tree Representation For P4-Sparse Graphs, B. Jamison, Stephan Olariu

Computer Science Faculty Publications

A graph G is P₄-sparse if no set of five vertices in G induces more than one chordless path of length three. P₄-sparse graphs generalize both the class of cographs and the class of P₄-reducible graphs. We give several characterizations for P₄-sparse graphs and show that they can be constructed from single-vertex graphs by a finite sequence of operations. Our characterization implies that the P₄-sparse graphs admit a tree representation unique up to isomorphism. Furthermore, this tree representation can be obtained in polynomial time.

On Sources In Comparability Graphs, With Applications, Stephan Olariu

Computer Science Faculty Publications

We characterize sources in comparability graphs and show that our result provides a unifying look at two recent results about interval graphs.

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.

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).

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 …

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.

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 …

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 …