Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 22 for “"Graph sparsification"”.
-
Graph Sparsification with Priority
Given a graph, a \emph{sparsification} is a smaller graph which approximates or preserves some property of the original graph. Well-known sparsifications include but are not limited to spanning trees (preserving connectivity), Steiner trees and forests (preserving connectivity between certain …
-
SUBLINEAR GRAPH SPARSIFICATION WITH APPLICATIONS TO CUTS, MATCHINGS, AND FLOWS
… sublinear algorithms for datasets with graph structures, such as social networks, biological networks and Web networks, where pairwise relationship between data points is captured. We obtain close-to-optimal results for the sublinear computation of several fundamental graph problems - …
-
FAST VERY-LARGE-SCALE INTEGRATED (VLSI) CIRCUITS SIMULATIONS
… cases. For circuit simulations, based on recent graph sparsification research, we propose a circuit-oriented general-purpose support-circuit preconditioning (GPSCP) approach to improve the matrix solving time and reduce the memory consumption during SPICE-accurate integrated circuit simulations. …
-
Analyzing Massive Graphs in the Semi-streaming Model
Massive graphs arise in a many scenarios, for example, traffic data analysis in large networks, large scale scientific experiments, and clustering of large data sets. The semi-streaming model was proposed for processing massive graphs. In the semi-streaming model, we have a random accessible memory …
-
HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS
… properties of eigenvalues and eigenvectors of graph Laplacians, more efficient algorithms can be developed for tackling many graph-related computing tasks. In this dissertation, spectral methods are utilized for achieving faster algorithms in the applications of very-large-scale integration …
-
A regularization perspective on spectral sparsification
… how to obtain faster algorithms for spectral graph sparsifi-cation by applying continuous optimization techniques. Spectral sparsification is thetask of reducing the number of edges in a graph while maintaining a spectral ap-proximation to the original graph. Our key conceptual contribution is …
-
Optimal Robust Sparse Networks: Algorithms for Maximizing Algebraic Connectivity in Robotic Applications
… as the robot must store accrued historical pose-graph information (representing relative pose measurements between nodes) in a lifelong SLAM application. An alternative to reducing the storage requirement is to process the accrued historical information and reduce the necessity to store the …
-
Randomized Primitives For Linear Algebra and Applications
… and applicability to matrix computations and graph theoretic problems. The thesis can be divided into three parts. The first part concentrates on the development of randomized linear algebraic primitives, the second part demonstrates the application of such primitives to matrix computations, …
-
Development and evaluation of machine learning algorithms for biomedical applications
… suitable for link prediction in gene networks; a graph sparsification method for network sampling; (iii) combined supervised and unsupervised methods to infer gene networks; and (iv) sampling and boosting techniques for reverse engineering gene networks. For drug sensitivity prediction problem, …
-
Collaborative Artificial Intelligence Algorithms for Medical Imaging Applications
… analysis, based on data clustering and graph sparsification. Then, we present a semi-supervised multi-task network for local analysis of image in radiologists' ROIs, extracted in the previous step. To address missing tumors and analyze regions that are completely missed by radiologists …
-
Sublinear Algorithm And Lower Bound For Combinatorial Problems
… algorithms in these models.We first consider two graph problems, vertex coloring problem and metric traveling salesman problem (TSP). The main results are structure results for these problems, which give frameworks for achieving sublinear algorithms of these problems in different models. We also …
-
Lossy Computation For Large-Scale Machine Learning
… or social networks where data is interconnected, Graph neural networks (GNNs) have recently emerged as one of the de-facto standard tools to analyze the graph data. Leveraging the message passing mechanism, GNNs learn the representation of each node by iteratively aggregating information from its …
-
SCALABLE INTEGRATED CIRCUIT SIMULATION ALGORITHMS FOR ENERGY-EFFICIENT TERAFLOP HETEROGENEOUS PARALLEL COMPUTING PLATFORMS
… introduces a novel transient-simulation guided graph sparsification technique, as well as an efficient runtime performance modeling approach tailored for heterogeneous manycore CPU-GPU computing system to build nearly-optimal subgraph preconditioners that can lead to minimum HB simulation …
-
Algorithmic advances in learning from large dimensional matrices and scientific data
… rank approximation, column subset selection, and graph sparsification. We present a new approach based on multilevel coarsening to compute these approximations for large sparse matrices and graphs. Lastly, on the linear algebra front, we devise a novel algorithm based on rank shrinkage for the …
-
Some inverse problems on finite networks
… it, which is based on techniques of spectral graph sparsification, and it is based on original results bounding the fitting error of a sparse approximation of a network. We show several experimental results in which we are able to recover a sparse network.
-
Combinatorially Thin Trees and Spectrally Thin Trees in Structured Graphs
Given a graph $G=(V,E)$, finding simpler estimates of $G$ with possibly fewer edges or vertices while capturing some of its specific properties has been used in order to design efficient algorithms. The concept of estimating a graph with a simpler graph is known as graph sparsification. Spanning …
-
Parallel and External-Memory Algorithms for Large-Scale Genomic Sequence-Graph and -Index Construction
… a mathematical object called the de Bruijn graph—and the associated data structure and variants—have become a compact data representation of increasing utility across computational genomics. Genomic data are expensive in terms of space, and building a compact representation of sequences of …
-
Improving the applicability of visual SLAM with submodular submatrix selection
… with two equivalent representations: factor graph and Jacobian matrix. From the perspective of information preservation, the full factor graph that contains many inter-connections between nodes should be used. However, for a real-time applicable SLAM, a small and sparse graph (Jacobian) is …
-
Application of nearly linear solvers to electric power system computation
… new theoretical method that is based on ideas in graph theory and combinatorics. The technique builds a chain of progressively smaller approximate systems with preconditioners based on the system's low stretch spanning tree. The method is compared to traditional linear solvers and shown to reduce …
-
Structural Similarity: Applications to Object Recognition and Clustering
… We address both node (local) similarity and graph (global) similarity. Concerning node similarity, we focus on improving the diffusive process leading to compute this similarity (e.g. Commute Times) by means of modifying or rewiring the structure of the graph (Graph Densification), although …
Page 1 of 2