Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Graph theory”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS1971

On a programming language for graph algorithms

An algorithmic language, GRAAL, is presented for describing and implementing graph algorithms of the type primarily arising in applications. The language is based on a set algebraic model of graph theory which defines the graph structure in terms of morphisms between certain set algebraic structures over the node set and arc set. GRAAL is modular in the sense that the user specifies which of these mappings are available with any graph. This allows flexibility in the selection of the storage representation for different graph structures. In line with its set theoretic foundation, the language introduces sets as a basic data type and provides for the efficient execution of all set and graph operators. At present, GRAAL is defined as an extension of ALGOL 60 (revised) and its formal description is given as a supplement to the syntactic and semantic definition of ALGOL. Several typical graph algorithms are written in GRAAL to illustrate various features of the language and to show its applicability.

Rheinboldt, W. C.↗
NASA NTRSDate not supplied

Cooperative Clustering Techniques For Space Network Scalability

Routing in the space internet must face many unique challenges - from unplanned disconnections and interruptions to predictable intermittent connectivity due to high network mobility and long propagation delays. NASA’s current approach to such routing is Contact Graph Routing (CGR), using a graph formed of prescheduled communication contacts to compute routes through the network. While this approach manages to tackle issues of connectivity and propagation delays, it is a global approach that requires continuous knowledge of the entire network. In a potential future Solar Space Internet (SSI) such an approach on its own cannot scale to large networks with thousands of members. In this paper we propose clustering as a solution to CGR scalability. Clustering has been used in many networking problems as a way to subdivide the network and allow for localized routing and better scalability. Using techniques from graph theory and game theory, we explore various existing clustering algorithms and adapt them to the Contact Graph Routing setting. We propose a way to combine multiple algorithms to create a Delay Tolerant Clustering Protocol (DTCP). In addition, we explore the underlying networking mechanisms such as multicast, neighbor discovery, and software defined networking that may be used to enable DTCP.

Delay Tolerant Networking↗
NASA NTRSDate not supplied

Cooperative Clustering Techniques Applied to Contact Graph Routing

Routing in the space internet has to face many unique challenges - from unplanned disconnections and interruptions to predictable intermittent connectivity due to high network mobility and long propagation delays. NASA’s current approach to such routing is Contact Graph Routing (CGR), using a graph formed of prescheduled communication contacts to compute routes through the network. While this approach manages to tackle issues of connectivity and propagation delays, it is a global approach that requires continuous knowledge of the entire network. In a potential future Solar Space Internet (SSI) such an approach on its own cannot scale to large networks with thousands of members. In this presentation we propose clustering as a solution to CGR scalability. Clustering has been used in many networking problems as a way to subdivide the network and allow for localized routing and better scalability. Using techniques from graph theory and game theory, we explore various existing clustering algorithms and adapt them to the Contact Graph Routing setting. Finally, we propose a way to combine multiple algorithms to create a Delay Tolerant Clustering Protocol.

Yael Kirkpatrick↗
NASA NTRS2002

Normalized Cut Algorithm for Automated Assignment of Protein Domains

We present a novel computational method for automatic assignment of protein domains from structural data. At the core of our algorithm lies a recently proposed clustering technique that has been very successful for image-partitioning applications. This grap.,l-theory based clustering method uses the notion of a normalized cut to partition. an undirected graph into its strongly-connected components. Computer implementation of our method tested on the standard comparison set of proteins from the literature shows a high success rate (84%), better than most existing alternative In addition, several other features of our algorithm, such as reliance on few adjustable parameters, linear run-time with respect to the size of the protein and reduced complexity compared to other graph-theory based algorithms, would make it an attractive tool for structural biologists.

Samanta, M. P.↗
NASA NTRS1990

Using minimal spanning trees to compare the reliability of network topologies

Graph theoretic methods are applied to compute the reliability for several types of networks of moderate size. The graph theory methods used are minimal spanning trees for networks with bi-directional links and the related concept of strongly connected directed graphs for networks with uni-directional links. A comparison is conducted of ring networks and braided networks. The case is covered where just the links fail and the case where both links and nodes fail. Two different failure modes for the links are considered. For one failure mode, the link no longer carries messages. For the other failure mode, the link delivers incorrect messages. There is a description and comparison of link-redundancy versus path-redundancy as methods to achieve reliability. All the computations are carried out by means of a fault tree program.

Leister, Karen J.↗
NASA NTRS2004

Network Theory: A Primer and Questions for Air Transportation Systems Applications

A new understanding (with potential applications to air transportation systems) has emerged in the past five years in the scientific field of networks. This development emerges in large part because we now have a new laboratory for developing theories about complex networks: The Internet. The premise of this new understanding is that most complex networks of interest, both of nature and of human contrivance, exhibit a fundamentally different behavior than thought for over two hundred years under classical graph theory. Classical theory held that networks exhibited random behavior, characterized by normal, (e.g., Gaussian or Poisson) degree distributions of the connectivity between nodes by links. The new understanding turns this idea on its head: networks of interest exhibit scale-free (or small world) degree distributions of connectivity, characterized by power law distributions. The implications of scale-free behavior for air transportation systems include the potential that some behaviors of complex system architectures might be analyzed through relatively simple approximations of local elements of the system. For air transportation applications, this presentation proposes a framework for constructing topologies (architectures) that represent the relationships between mobility, flight operations, aircraft requirements, and airspace capacity, and the related externalities in airspace procedures and architectures. The proposed architectures or topologies may serve as a framework for posing comparative and combinative analyses of performance, cost, security, environmental, and related metrics.

Holmes, Bruce J.↗
NASA NTRS2002

An Efficient Scheme for Updating Sparse Cholesky Factors

Raghavan had earlier developed the software package DCSPACK which can be used for solving sparse linear systems where the coefficient matrix is symmetric and positive definite (this project was not funded by NASA but by agencies such as NSF). DSCPACK-S is the serial code and DSCPACK-P is a parallel implementation suitable for multiprocessors or networks-of-workstations with message passing using MCI. The main algorithm used is the Cholesky factorization of a sparse symmetric positive positive definite matrix A = LL(T). The code can also compute the factorization A = LDL(T). The complexity of the software arises from several factors relating to the sparsity of the matrix A. A sparse N x N matrix A has typically less that cN nonzeroes where c is a small constant. If the matrix were dense, it would have O(N2) nonzeroes. The most complicated part of such sparse Cholesky factorization relates to fill-in, i.e., zeroes in the original matrix that become nonzeroes in the factor L. An efficient implementation depends to a large extent on complex data structures and on techniques from graph theory to reduce, identify, and manage fill. DSCPACK is based on an efficient multifrontal implementation with fill-managing algorithms and implementation arising from earlier research by Raghavan and others. Sparse Cholesky factorization is typically a four step process: (1) ordering to compute a fill-reducing numbering, (2) symbolic factorization to determine the nonzero structure of L, (3) numeric factorization to compute L, and, (4) triangular solution to solve L(T)x = y and Ly = b. The first two steps are symbolic and are performed using the graph of the matrix. The numeric factorization step is of dominant cost and there are several schemes for improving performance by exploiting the nested and dense structure of groups of columns in the factor. The latter are aimed at better utilization of the cache-memory hierarchy on modem processors to prevent cache-misses and provide execution rates (operations/second) that are close to the peak rates for dense matrix computations. Currently, EPISCOPACY is being used in an application at NASA directed by J. Newman and M. James. We propose the implementation of efficient schemes for updating the LL(T) or LDL(T) factors computed in DSCPACK-S to meet the computational requirements of their project. A brief description is provided in the next section.

Raghavan, Padma↗
NASA NTRS1978

The Lovasz bound and some generalizations

The zero error capacity of a discrete memoryless channel is defined as the largest rate at which information can be transmitted over the channel with zero error probability. One channel with five inputs and outputs whose zero capacity remained unsolved until very recently is considered. An extremely powerful and general technique phased in terms of graph theory, for studying combinatorial packing problems is presented. In particular, Delsarte's linear programming bound for cliques in association schemes appears as a special case of the Lovasz bound.

Mceliece, R. J.↗
NASA NTRS1978

A model for dynamic allocation of human attention among multiple tasks

The problem of multi-task attention allocation with special reference to aircraft piloting is discussed with the experimental paradigm used to characterize this situation and the experimental results obtained in the first phase of the research. A qualitative description of an approach to mathematical modeling, and some results obtained with it are also presented to indicate what aspects of the model are most promising. Two appendices are given which (1) discuss the model in relation to graph theory and optimization and (2) specify the optimization algorithm of the model.

Sheridan, T. B.↗
NASA NTRS1981

The dynamics and control of large flexible space structures-IV

The effects of solar radiation pressure as the main environmental disturbance torque were incorporated into the model of the rigid orbiting shallow shell and computer simulation results indicate that within the linear range the rigid modal amplitudes are excited in proportion to the area to mass ratio. The effect of higher order terms in the gravity-gradient torque expressions previously neglected was evaluated and found to be negligible for the size structures under consideration. A graph theory approach was employed for calculating the eigenvalues of a large flexible system by reducing the system (stiffness) matrix to lower ordered submatrices. The related reachability matrix and term rank concepts are used to verify controllability and can be more effective than the alternate numerical rank tests. Control laws were developed for the shape and orientation control of the orbiting flexible shallow shell and numerical results presented.

Bainum, P. M.↗
NASA NTRS1982

The dynamics and control of large flexible space structures-V

A general survey of the progress made in the areas of mathematical modelling of the system dynamics, structural analysis, development of control algorithms, and simulation of environmental disturbances is presented. The use of graph theory techniques is employed to examine the effects of inherent damping associated with LSST systems on the number and locations of the required control actuators. A mathematical model of the forces and moments induced on a flexible orbiting beam due to solar radiation pressure is developed and typical steady state open loop responses obtained for the case when rotations and vibrations are limited to occur within the orbit plane. A preliminary controls analysis based on a truncated (13 mode) finite element model of the 122m. Hoop/Column antenna indicates that a minimum of six appropriately placed actuators is required for controllability. An algorithm to evaluate the coefficients which describe coupling between the rigid rotational and flexible modes and also intramodal coupling was developed and numerical evaluation based on the finite element model of Hoop/Column system is currently in progress.

Bainum, P. M.↗
NASA NTRS1984

Generalized serial search code acquisition - The equivalent circular state diagram approach

A transform-domain method for deriving the generating function of the acquisition process resulting from an arbitrary serial search strategy is presented. The method relies on equivalent circular state diagrams, uses Mason's formula from flow-graph theory, and employs a minimum number of required parameters. The transform-domain approach is briefly described and the concept of equivalent circular state diagrams is introduced and exploited to derive the generating function and resulting mean acquisition time for three particular cases of interest, the continuous/center Z search, the broken/center Z search, and the expanding window search. An optimization of the latter technique is performed whereby the number of partial windows which minimizes the mean acquisition time is determined. The numerical results satisfy certain intuitive predictions and provide useful design guidelines for such systems.

Polydoros, A.↗
NASA NTRS1986

Elimination sequence optimization for SPAR

SPAR is a large-scale computer program for finite element structural analysis. The program allows user specification of the order in which the joints of a structure are to be eliminated since this order can have significant influence over solution performance, in terms of both storage requirements and computer time. An efficient elimination sequence can improve performance by over 50% for some problems. Obtaining such sequences, however, requires the expertise of an experienced user and can take hours of tedious effort to affect. Thus, an automatic elimination sequence optimizer would enhance productivity by reducing the analysts' problem definition time and by lowering computer costs. Two possible methods for automating the elimination sequence specifications were examined. Several algorithms based on the graph theory representations of sparse matrices were studied with mixed results. Significant improvement in the program performance was achieved, but sequencing by an experienced user still yields substantially better results. The initial results provide encouraging evidence that the potential benefits of such an automatic sequencer would be well worth the effort.

Hogan, Harry A.↗
NASA NTRS1990

Space station advanced automation

In the development of a safe, productive and maintainable space station, Automation and Robotics (A and R) has been identified as an enabling technology which will allow efficient operation at a reasonable cost. The Space Station Freedom's (SSF) systems are very complex, and interdependent. The usage of Advanced Automation (AA) will help restructure, and integrate system status so that station and ground personnel can operate more efficiently. To use AA technology for the augmentation of system management functions requires a development model which consists of well defined phases of: evaluation, development, integration, and maintenance. The evaluation phase will consider system management functions against traditional solutions, implementation techniques and requirements; the end result of this phase should be a well developed concept along with a feasibility analysis. In the development phase the AA system will be developed in accordance with a traditional Life Cycle Model (LCM) modified for Knowledge Based System (KBS) applications. A way by which both knowledge bases and reasoning techniques can be reused to control costs is explained. During the integration phase the KBS software must be integrated with conventional software, and verified and validated. The Verification and Validation (V and V) techniques applicable to these KBS are based on the ideas of consistency, minimal competency, and graph theory. The maintenance phase will be aided by having well designed and documented KBS software.

Woods, Donald↗
NASA NTRS1989

Power flow for spacecraft power systems

A method for constructing the generalized system-level admittance matrix for use with a Newton-Raphson power flow is presented. The network modeling technique presented does not use the standard pi-equivalent models, which assume a lossless return path, for the transmission line and transformer. If the return path cannot be assumed lossless, then the standard algorithms for constructing the system admittance matrix cannot be used. The method presented here uses concepts from linear graph theory to combine network modules to form the system-level admittance matrix. The modeling technique is presented, and the resulting matrix is used with a standard Newton-Raphson power flow to calculate all system voltages and current (power) flows.

Halpin, S. M.↗
NASA NTRS1992

Single-phase power distribution system power flow and fault analysis

Alternative methods for power flow and fault analysis of single-phase distribution systems are presented. The algorithms for both power flow and fault analysis utilize a generalized approach to network modeling. The generalized admittance matrix, formed using elements of linear graph theory, is an accurate network model for all possible single-phase network configurations. Unlike the standard nodal admittance matrix formulation algorithms, the generalized approach uses generalized component models for the transmission line and transformer. The standard assumption of a common node voltage reference point is not required to construct the generalized admittance matrix. Therefore, truly accurate simulation results can be obtained for networks that cannot be modeled using traditional techniques.

Halpin, S. M.↗
NASA NTRS1994

Weighted graph based ordering techniques for preconditioned conjugate gradient methods

We describe the basis of a matrix ordering heuristic for improving the incomplete factorization used in preconditioned conjugate gradient techniques applied to anisotropic PDE's. Several new matrix ordering techniques, derived from well-known algorithms in combinatorial graph theory, which attempt to implement this heuristic, are described. These ordering techniques are tested against a number of matrices arising from linear anisotropic PDE's, and compared with other matrix ordering techniques. A variation of RCM is shown to generally improve the quality of incomplete factorization preconditioners.

Clift, Simon S.↗
NASA NTRS2005

A Comparison of Geographic Information Systems, Complex Networks, and Other Models for Analyzing Transportation Network Topologies

This report reviews six classes of models that are used for studying transportation network topologies. The report is motivated by two main questions. First, what can the "new science" of complex networks (scale-free, small-world networks) contribute to our understanding of transport network structure, compared to more traditional methods? Second, how can geographic information systems (GIS) contribute to studying transport networks? The report defines terms that can be used to classify different kinds of models by their function, composition, mechanism, spatial and temporal dimensions, certainty, linearity, and resolution. Six broad classes of models for analyzing transport network topologies are then explored: GIS; static graph theory; complex networks; mathematical programming; simulation; and agent-based modeling. Each class of models is defined and classified according to the attributes introduced earlier. The paper identifies some typical types of research questions about network structure that have been addressed by each class of model in the literature.

Alexandrov, Natalia↗