Search NASA⌕ Search

SEARCH · Search NASA

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 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
DOE OSTI2026

Grid Topology Discovery Algorithm Evaluation of Suitability for Utility Deployment (CRADA 606 Final Report)

This work presents the results of a field-informed demonstration aimed at evaluating the practical suitability of a topology discovery algorithm for utility environments. We demonstrated an algorithm that uses a graph-theory-informed state estimation approach for model selection. In collaboration with Survalent and Peninsula Light Co., the algorithm was applied to real feeder models and field measurements from supervisory control and data acquisition (SCADA) and advanced metering infrastructure (AMI) systems to identify the operational topology of a power distribution system. The demonstration assessed the algorithm’s performance under realistic data conditions, including sparse and noisy measurements, and examined its ability to identify the most likely network configurations. The results confirmed that the approach can effectively narrow down feasible topologies, providing operators with improved situational awareness of network status. Key lessons learned emphasize the need for systematic data validation and strategic sensor placement to enhance observability. These insights inform future deployment strategies and guide refinements for broader adoption in utility operations.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2025

Efficient Hamiltonian encoding algorithms for extracting quantum control mechanism as interfering pathway amplitudes in the Dyson series

Hamiltonian encoding is a methodology for revealing the mechanism behind the dynamics governing controlled quantum systems. In this paper, following Mitra and Rabitz \cite{abhra_1}, we define mechanism via pathways of eigenstates that describe the evolution of the system, where each pathway is associated with a complex-valued amplitude corresponding to a term in the Dyson series. The evolution of the system is determined by the constructive and destructive interference of these pathway amplitudes. Pathways with similar attributes can be grouped together into pathway classes. The amplitudes of pathway classes are computed by modulating the Hamiltonian matrix elements and decoding the subsequent evolution of the system rather than by direct computation of the individual terms in the Dyson series. The original implementation of Hamiltonian encoding was computationally intensive and became prohibitively expensive in large quantum systems. This paper presents two new encoding algorithms that calculate the amplitudes of pathway classes by using techniques from graph theory and algebraic topology to exploit patterns in the set of allowed transitions, greatly reducing the number of matrix elements that need to be modulated. These new algorithms provide an exponential decrease in both computation time and memory utilization with respect to the Hilbert space dimension of the system. To demonstrate the use of these techniques, they are applied to two illustrative state-to-state transition problems.

Abrams, Erez [Princeton University, Massachusetts ↗
DOE OSTI2021

Design, Synthesis, and Utility of Defined Molecular Scaffolds

A growing theme in chemistry is the joining of multiple organic molecular building blocks to create functional molecules. Diverse derivatizable structures—here termed “scaffolds” comprised of “hubs”—provide the foundation for systematic covalent organization of a rich variety of building blocks. This review encompasses 30 tri- or tetra-armed molecular hubs (e.g., triazine, lysine, arenes, dyes) that are used directly or in combination to give linear, cyclic, or branched scaffolds. Each scaffold is categorized by graph theory into one of 31 trees to express the molecular connectivity and overall architecture. Rational chemistry with exacting numbers of derivatizable sites is emphasized. The incorporation of water-solubilization motifs, robust or self-immolative linkers, enzymatically cleavable groups and functional appendages affords immense (and often late-stage) diversification of the scaffolds. Altogether, 107 target molecules are reviewed along with 19 syntheses to illustrate the distinctive chemistries for creating and derivatizing scaffolds. The review covers the history of the field up through 2020, briefly touching on statistically derivatized carriers employed in immunology as counterpoints to the rationally assembled and derivatized scaffolds here, although most citations are from the past two decades. The scaffolds are used widely in fields ranging from pure chemistry to artificial photosynthesis and biomedical sciences.

Sato, Daisuke (ORCID:0000000305472659)↗
DOE OSTI2021

Automated Detection of Instability-Inducing Channel Geometry Transitions in Saint-Venant Simulation of Large-Scale River Networks

A new sweep-search algorithm (SSA) is developed and tested to identify the channel geometry transitions responsible for numerical convergence failure in a Saint-Venant equation (SVE) simulation of a large-scale open-channel network. Numerical instabilities are known to occur at “sharp” transitions in discrete geometry, but the identification of problem locations has been a matter of modeler’s art and a roadblock to implementing large-scale SVE simulations. The new method implements techniques from graph theory applied to a steady-state 1D shallow-water equation solver to recursively examine the numerical stability of each flowpath through the channel network. The SSA is validated with a short river reach and tested by the simulation of ten complete river systems of the Texas–Gulf Coast region by using the extreme hydrological conditions recorded during hurricane Harvey. The SSA successfully identified the problematic channel sections in all tested river systems. Subsequent modification of the problem sections allowed stable solution by an unsteady SVE numerical solver. The new SSA approach permits automated and consistent identification of problem channel geometry in large open-channel network data sets, which is necessary to effectively apply the fully dynamic Saint-Venant equations to large-scale river networks or for city-wide stormwater networks.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2020

Approximate Inverse Chain Preconditioner: Iteration Count Case Study for Spectral Support Solvers

As the growing availability of computational power slows, there has been an increasing reliance on algorithmic advances. However, faster algorithms alone will not necessarily bridge the gap in allowing computational scientists to study problems at the edge of scientific discovery in the next several decades. Often, it is necessary to simplify or precondition solvers to accelerate the study of large systems of linear equations commonly seen in a number of scientific fields. Preconditioning a problem to increase efficiency is often seen as the best approach; yet, preconditioners which are fast, smart, and efficient do not always exist. Following the progress of [1], we present a new preconditioner for symmetric diagonally dominant (SDD) systems of linear equations. These systems are common in certain PDEs, network science, and supervised learning among others. Based on spectral support graph theory, this new preconditioner builds off of the work of [2], computing and applying a V-cycle chain of approximate inverse matrices. This preconditioner approach is both algebraic in nature as well as hierarchically-constrained depending on the condition number of the system to be solved. Due to its generation of an Approximate Inverse Chain of matrices, we refer to this as the AIC preconditioner. We further accelerate the AIC preconditioner by utilizing precomputations to simplify setup and multiplications in the con-text of an iterative Krylov-subspace solver. While these iterative solvers can greatly reduce solution time, the number of iterations can grow large quickly in the absence of good preconditioners. Initial results for the AIC preconditioner have shown a very large reduction in iteration counts for SDD systems as compared to standard preconditioners such as Incomplete Cholesky (ICC) and Multigrid (MG). We further show significant reduction in iteration counts against the more advanced Combinatorial Multigrid (CMG) preconditioner. We have further developed no-fill sparsification techniques to ensure that the computational cost of applying the AIC preconditioner does not grow prohibitively large as the depth of the V-cycle grows for systems with larger condition numbers. Our numerical results have shown that these sparsifiers maintain the sparsity structure of our system while also displaying significant reductions in iteration counts.1 2

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Approximate Inverse Chain Preconditioner: Iteration Count Case Study for Spectral Support Solvers

As the growing availability of computational power slows, there has been an increasing reliance on algorithmic advances. However, faster algorithms alone will not necessarily bridge the gap in allowing computational scientists to study problems at the edge of scientific discovery in the next several decades. Often, it is necessary to simplify or precondition solvers to accelerate the study of large systems of linear equations commonly seen in a number of scientific fields. Preconditioning a problem to increase efficiency is often seen as the best approach; yet, preconditioners which are fast, smart, and efficient do not always exist. Following the progress of [1], we present a new preconditioner for symmetric diagonally dominant (SDD) systems of linear equations. These systems are common in certain PDEs, network science, and supervised learning among others. Based on spectral support graph theory, this new preconditioner builds off of the work of [2], computing and applying a V-cycle chain of approximate inverse matrices. This preconditioner approach is both algebraic in nature as well as hierarchically-constrained depending on the condition number of the system to be solved. Due to its generation of an Approximate Inverse Chain of matrices, we refer to this as the AIC preconditioner. We further accelerate the AIC preconditioner by utilizing precomputations to simplify setup and multiplications in the con-text of an iterative Krylov-subspace solver. While these iterative solvers can greatly reduce solution time, the number of iterations can grow large quickly in the absence of good preconditioners. Initial results for the AIC preconditioner have shown a very large reduction in iteration counts for SDD systems as compared to standard preconditioners such as Incomplete Cholesky (ICC) and Multigrid (MG). We further show significant reduction in iteration counts against the more advanced Combinatorial Multigrid (CMG) preconditioner. We have further developed no-fill sparsification techniques to ensure that the computational cost of applying the AIC preconditioner does not grow prohibitively large as the depth of the V-cycle grows for systems with larger condition numbers. Our numerical results have shown that these sparsifiers maintain the sparsity structure of our system while also displaying significant reductions in iteration counts.1 2

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Fundamental Path Optimization Strategies for Extrusion-based Additive Manufacturing

Extrusion-based additive manufacturing processes begin with a software program, called a slicer, that generates layer geometry and fits toolpaths to each layer to define where material is to be extruded or deposited. Before the toolpaths are output as g-code for the additive manufacturing system to execute, the toolpaths should be optimized. Many complex optimization approaches using graph theory, Chinese postman problem, and other complex mathematical models exist, but these approaches are rarely used in daily printing operations and are not available through common slicing programs such as Cura and PrusaSlicer. Instead, path planning and optimization typically revolves around simpler, fully automated approaches such as inside out and next closest. This paper will explore the fundamental optimization strategies for toolpath planning and document a new implementation, available via open-source slicing software, that allows for greater control of the path planning process.

Roschli, Alex [ORNL] (ORCID:0000000213084632)↗
DOE OSTI2020

The concept of spin ice graphs and a field theory for their charges

Originally detected in rare earth pyrochlores, spin ice physics is now being artificially extended to a variety of geometries that control collective behavior and exotic properties, making graph theory their proper framework. We relate spin ice notions, such as ice rule, ice manifold, Coulomb phases, charges, and monopoles, to graph-theoretical notions, such as balance, in/out-degrees, and Euler paths. We then propose a field-theoretical treatment in which topological charges and monopoles are the degrees of freedom, while the binary spins are subsumed in an entropic interaction among charges. We show that for a spin ice on a graph in a Gaussian approximation, the kernel of the entropic interaction is the inverse of the graph Laplacian, and we compute screening functions from the graph spectra as Green operators for the screened Poisson problem on a graph. We then apply the treatment to star graphs, tournaments, cycles, and regular spin ice in different dimensions. Our aim is twofold: to set spin ice physics in a proper graph setting, where only topological rather than geometrical notions hold, and to invite graph theorists to contribute their powerful tools to the field of spin ice.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2023

Graph-based quantum response theory and shadow Born–Oppenheimer molecular dynamics

Graph-based linear scaling electronic structure theory for quantum-mechanical molecular dynamics simulations [A. M. N. Niklasson et al., J. Chem. Phys. 144, 234101 (2016)] is adapted to the most recent shadow potential formulations of extended Lagrangian Born–Oppenheimer molecular dynamics, including fractional molecular-orbital occupation numbers [A. M. N. Niklasson, J. Chem. Phys. 152, 104103 (2020) and A. M. N. Niklasson, Eur. Phys. J. B 94, 164 (2021)], which enables stable simulations of sensitive complex chemical systems with unsteady charge solutions. The proposed formulation includes a preconditioned Krylov subspace approximation for the integration of the extended electronic degrees of freedom, which requires quantum response calculations for electronic states with fractional occupation numbers. For the response calculations, we introduce a graph-based canonical quantum perturbation theory that can be performed with the same natural parallelism and linear scaling complexity as the graph-based electronic structure calculations for the unperturbed ground state. Further, the proposed techniques are particularly well-suited for semi-empirical electronic structure theory, and the methods are demonstrated using self-consistent charge density-functional tight-binding theory both for the acceleration of self-consistent field calculations and for quantum-mechanical molecular dynamics simulations. Graph-based techniques combined with the semi-empirical theory enable stable simulations of large, complex chemical systems, including tens-of-thousands of atoms.

74 ATOMIC AND MOLECULAR PHYSICS↗
DOE OSTI2022

Hydrogen bond arrangements in (H 2 O) 20, 24, 28 clathrate hydrate cages: Optimization and many-body analysis

Here we provide a detailed study of hydrogen bonding arrangements, relative stability, residual entropy, and an analysis of the many-body effects in the (H 2 O) 20 (D-cage), (H 2 O) 24 (T-cage), and (H 2 O) 28 (H-cage) hollow cages making up structures I (sI) and II (sII) of clathrate hydrate lattices. Based on the enumeration of the possible hydrogen bonding networks for a fixed oxygen atom scaffold, the residual entropy (S 0 ) of these three gas phase cages was estimated at 0.754 82, 0.754 44, and 0.754 17 · Nk b , where N is the number of molecules and k b is Boltzmann’s constant. A previously identified descriptor of enhanced stability based on the relative arrangement and connectivity of nearest-neighbor fragments on the polyhedral water cluster [strong-weak-effective-bond model] also applies to the larger hollow cages. The three cages contain a maximum of 7, 9, and 11 such preferable arrangements of trans nearest dimer pairs with one “free” OH bond on the donor molecule (t1d dimers). The Many-Body Expansion (MBE) up to the 4-body suggests that the many-body terms vary nearly linearly with the cluster binding energy. Using a hierarchical approach of screening the relative stability of networks starting from optimizations with the TIP4P, TTM2.1-F, and MB-pol classical potentials, subsequently refining at more accurate levels of electronic structure theory (DFT and MP2), and finally correcting for zero-point energy, we were able to identify a group of four low-lying isomers of the (H 2 O) 24 T-cage, two of which are antisymmetric and the other two form a pair of antipode configurations.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2021

Dynamic Interference Management for UAV-Assisted Wireless Networks

Here, we investigate a transmission mechanism aiming to improve the data rate between a base station (BS) and a user equipment (UE) through deploying multiple relaying UAVs. We consider the effect of interference incurred by another established communication network, which makes our problem challenging and different from the state of the art. We aim to design the 3D trajectories and power allocation for the UAVs to maximize the data flow of the network while keeping the interference on the existing communication network below a threshold. We utilize the mobility feature of the UAVs to evade the (un)-intended interference caused by (un)-intentional interferers. To this end, we propose an alternating-maximization approach to jointly obtain the 3D trajectories and the UAVs transmission powers. We handle the 3D trajectory design by resorting to spectral graph the power allocation through convex optimization techniques. We also approach the problem from the intentional interferer’s perspective where smart jammers chase the UAVs to effectively degrade the data flow of the network. We also extend our work to the case for multiple UEs. Finally, we demonstrate the efficacy of our proposed method through extensive simulations.

42 ENGINEERING↗
DOE OSTI2025

Quantum graph learning and algorithms applied in quantum computer sciences and image classification

Graph and network theory play a fundamental role in quantum computer sciences, including quantum information and computation. Random graphs and complex network theory are pivotal in predicting novel quantum phenomena, where entangled links are represented by edges. Quantum algorithms have been developed to enhance solutions for various network problems, giving rise to quantum graph computing and quantum graph learning (QGL). Here, in this review, we explore graph theory and graph learning methods as powerful tools for quantum computers to generate efficient solutions to problems beyond the reach of classical systems. We delve into the development of quantum complex network theory and its applications in quantum computation, materials discovery, and research. We also discuss quantum machine learning (QML) methodologies for effective image classification using qubits, quantum gates, and quantum circuits. Additionally, the paper addresses the challenges of QGL and algorithms, emphasizing the steps needed to develop flexible QGL solvers. This review presents a comprehensive overview of the fields of QGL and QML, highlights recent advancements, and identifies opportunities for future research.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

DyG-DPCD: A Distributed Parallel Community Detection Algorithm for Large-Scale Dynamic Graphs

Dynamic (Temporal) graphs capture the valuable evolution of real-world systems, from the continuously evolving patterns of social interactions and genetic pathways to the dynamic fluctuations of economic forces. Detecting communities for such evolving networks poses unique challenges. Detecting and analyzing the evolution of communities within dynamic graphs unlocks valuable insights into the underlying structural and temporal patterns of real-world systems. However, the sheer volume of modern graph data and the inherent complexity of the temporal dimension pose significant challenges to scalable community detection algorithms. Addressing this gap, our work explores the limited landscape of scalable distributed-memory parallel methods specifically designed for dynamic network community detection. We propose a novel parallel algorithm, DyG-DPCD (Dynamic Graph Distributed Parallel Community Detection), to detect communities in dynamic networks using the Message Passing Interface (MPI) framework. We present a vertex-centric approach, allowing us to detect communities through local optimization. Furthermore, we enhance our baseline algorithm by incorporating three heuristics, which improve the algorithm’s performance significantly while maintaining the quality of the solutions. We demonstrate the efficiency of our algorithm by experimenting on several real-world large-scale networks with hundreds of millions of edges spanning diverse domains. Notably, DyG-DPCD achieves speedups between 25× and 30× for large networks that we experimented on using NERSC compute nodes. In conclusion, our algorithm outperforms the STINGER parallel re-agglomeration algorithm by 30×.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Knowledge Graph for End-to-End Traceability of an Integrated Human-Earth System Model

Integrated human-Earth system models inform energy-water-land system dynamics and policies, yet their results are difficult to trace through input-data, model structure, scenario configurations, and solved outputs. Because this information is siloed across disconnected artifacts, process-based IAMs have historically lacked a unified, queryable representation. Such lack of traceability prevents researchers from systematically isolating the multi-sector drivers of complex outcomes (such as tracing water-scarcity results back to distant energy-system dynamics) or conducting holistic uncertainty attribution across hundreds of interacting parameters. To address this concern, our work documents the software engineering process of a knowledge graph that unifies these four layers for the Global Change Analysis Model (GCAM-USA_Reference scenario, GCAM v9.1). The graph was built as a relational property graph in DuckDB from the run’s own artifacts: the input-preparation dependency map (gcamdata chunk map), the model’s XML input files, the run configuration, and the results database (BaseX), successfully mapping the model’s declared structure. The resulting graph comprises 204,321 nodes and 1,687,814 edges across 16 node types and 15 edge types, with approximately 16.3 million time-series values stored separately to maintain structural efficiency. To ensure representation fidelity, every edge carries an epistemic-status annotation recording the warrant for the relationship (structural, provenance, dependency, or model-derived), and a machine-readable provenance ledger classifying the origin of every schema element. Evaluation against a fixed five-benchmark suite with locked baselines reports zero structural orphans, zero dangling edge endpoints, and 100% of output-producing technologies traceable to raw input files. Two interactive interfaces present the graph, including a serverless browser application built on DuckDB-Wasm. By establishing the first end-to-end provenance framework for an IAM, this work enables researchers and scientists to systematically audit complex policy scenarios, debug model structures, and trace policy-relevant outputs to their data origins in real time.

Artifical Intelligence↗
DOE OSTI2025

Ca X ML: Chemistry‐informed machine learning explains mutual changes between protein conformations and calcium ions in calcium‐binding proteins using structural and topological features

Proteins' flexibility is a feature in communicating changes in cell signaling instigated by binding with secondary messengers, such as calcium ions, associated with the coordination of muscle contraction, neurotransmitter release, and gene expression. When binding with the disordered parts of a protein, calcium ions must balance their charge states with the shape of calcium-binding proteins and their versatile pool of partners depending on the circumstances they transmit. Accurately determining the ionic charges of those ions is essential for understanding their role in such processes. However, it is unclear whether the limited experimental data available can be effectively used to train models to accurately predict the charges of calcium-binding protein variants. Here, we developed a chemistry-informed, machine-learning algorithm that implements a game theoretic approach to explain the output of a machine-learning model without the prerequisite of an excessively large database for high-performance prediction of atomic charges. We used the ab initio electronic structure data representing calcium ions and the structures of the disordered segments of calcium-binding peptides with surrounding water molecules to train several explainable models. Network theory was used to extract the topological features of atomic interactions in the structurally complex data dictated by the coordination chemistry of a calcium ion, a potent indicator of its charge state in protein. Our design created a computational tool of Ca X ML, which provided a framework of explainable machine learning model to annotate ionic charges of calcium ions in calcium-binding proteins in response to the chemical changes in an environment. Our framework will provide new insights into protein design for engineering functionality based on the limited size of scientific data in a genome space.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2024

Equivariant, safe and sensitive — graph networks for new physics

This study introduces a novel Graph Neural Network (GNN) architecture that leverages infrared and collinear (IRC) safety and equivariance to enhance the analysis of collider data for Beyond the Standard Model (BSM) discoveries. By integrating equivariance in the rapidity-azimuth plane with IRC-safe principles, our model significantly reduces computational overhead while ensuring theoretical consistency in identifying BSM scenarios amidst Quantum Chromodynamics backgrounds. The proposed GNN architecture demonstrates superior performance in tagging semi-visible jets, highlighting its potential as a robust tool for advancing BSM search strategies at high-energy colliders.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2021

Spectral Threshold for Extremal Cyclic Edge-Connectivity

In this report, the cyclic edge-connectivity of a graph G is the least k such that there exists a set of k edges whose removal disconnects G into components where every component contains a cycle. We show that for graphs of minimum degree at least 3 and girth g at least 4, the cyclic edge-connectivity is bounded above by (Δ-2)g where Δ is the maximum degree. We then prove that if the second eigenvalue of the adjacency matrix of a d-regular graph of girth g ≥ 4 is sufficiently small, then the cyclic edge-connectivity is (d-2)g, providing a spectral condition for when this upper bound on cyclic edge-connectivity is tight.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Graph-Based Modeling and Decomposition of Hierarchical Optimization Problems

We present a graph-theoretic modeling approach for hierarchical optimization that leverages the OptiGraph abstraction implemented in the Julia package Plasmo.jl. We show that the abstraction is flexible and can effectively capture complex hierarchical connectivity that arises from decision-making over multiple spatial and temporal scales (e.g., integration of planning, scheduling, and operations in manufacturing and infrastructures). We also show that the graph abstraction facilitates the conceptualization and implementation of decomposition and approximation schemes. Specifically, we propose a graph-based Benders decomposition (gBD) framework that enables the exploitation of hierarchical (nested) structures and that uses graph aggregation/partitioning procedures to discover such structures. In addition, we provide a Julia implementation of gBD, which we call PlasmoBenders.jl. We illustrate the capabilities using examples arising in the context of energy and power systems.

97 MATHEMATICS AND COMPUTING↗