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 18 of 18 for “"breadth-first search"”.
-
Breadth-first search for social network graphs on heterogenous platforms
DSpace SAF Submission Ingestion Package generated from Vireo submission #9220 on 2016-07-07 at 13:30:40
-
Design and analysis of a nondeterministic parallel breadth-first search algorithm
… have developed a multithreaded implementation of breadth-first search (BFS) of a sparse graph using the Cilk++ extensions to C++. My PBFS program on a single processor runs as quickly as a standard C++ breadth-first search implementation. PBFS achieves high workefficiency by using a novel …
-
A reformulated approach to attribute-aware sampling on large networks
… a different way to sample. Algorithms like Breadth first search, Random walk, Expansion sampling, or other related strategies fulfill this role currently. But these algorithms are focused mainly on ensuring properties based on the structure of the graph, without consideration for the …
-
Spatial Accelerator Generation and Optimization for Tensor Applications
… by a minimum-spanning-tree-based algorithm and a breadth-first-search-based heuristic algorithm for merging different spatial dataflow designs. LEGO back end then translates the hardware in a primitive-level graph to perform lower-level optimizations, and applies a set of linear-programming …
-
Data parallel algebraic multigrid
… Our formulation is performed in two phases, the first building on high-level generic abstractions to construct our solver in a architecture agnostic manner. Though effective we show that performance is severely limited by irregular sparse matrix operations, most notably sparse matrix-matrix …
-
Towards Efficient Autonomous Vehicle Systems: A Multi-Layer Approach
… coordination. A scheduling algorithm based on breadth-first search achieves up to 16.3% reduction in intersection evacuation time and 27.7% improvement in traffic efficiency. At the application layer, a 1-opt local search-based scheduling framework is proposed for non-preemptive real-time …
-
A concurrent architecture for a travel planning application
… of the optimal solution, because a bounded, breadth-first search strategy is used. The system also loses on performance because of additional overhead incurred by object collaboration. On the other hand, our architecture offers potential performance enhancements achievable through concurrency …
-
Distributed synchronizers in network simulator (Ns) software
… itself is an asynchronous algorithm; In this research, we experiment with different types of synchronizers. We implement them by considering two applications: leader election and breadth-first search algorithms. The algorithms are implemented on arbitrary networks. We compare the algorithms in …
-
New strategies for electronic design automation problems
… in PCB routing, the escape routing problem. Our first strategy is to use Boolean satisfiability to optimally solve the escape routing problem on one PCB component. Our second strategy is to use a novel boundary routing methodology to finish escape routing from two connected PCB components …
-
Directed search for the verification of communication protocols
… applies reachability algorithms like <br>depth-first, and breadth-first search for this purpose. Breadth-first <br>search is, in general, not memory-efficient, but offers shortest <br>counterexamples. On the other hand, depth-first search is more <br>memory-efficient, but delivers suboptimal …
-
Prefetching for complex memory access patterns
… This thesis makes three contributions. I first contribute an automated software prefetching compiler technique to insert high-performance prefetches into program code to bring data into the cache early, achieving 1.3x geometric mean speedup on the most complex processors, and 2.7x on the …
-
Performance engineering of multicore software : developing a science of fast code for the post-Moore era
… in practice: - PBFS, a work-efficient parallel breadth-first search algorithm. - The Prism chromatic-scheduling algorithm, which executes dynamic data-graph computations deterministically in parallel. - Ordering heuristics for parallel greedy graph coloring algorithms. - The pedigree mechanism …
-
Test-driven fault navigation for debugging reproducible failures
… even when using the scientific method, the search for failure causes can still be a laborious task. First, lacking expertise about the system makes it hard to understand incorrect behavior and to create reasonable hypotheses. Second, contemporary debugging approaches provide no or only …
-
Computing Paths in Massive Graphs
… path-related queries in massive graphs. First, we study how to efficiently process reachability queries on distributed graphs, which check whether there is a path from one vertex to another. Real-world massive graphs are typically distributed across multiple data centers due to their …
-
Strategies for Performance and Quality Improvement of Hardware Verification and Synthesis Algorithms
… consistent enormous gross challenges different research areas in Electronic Design Automation (EDA). Thus, various EDA applications such as equivalence checking, model checking, Automatic Test Pattern Generation (ATPG), functional Bi-decomposition, and technology mapping need to keep pace with …
-
Multi agent system for web database processing, on data extraction from online social networks.
… and quantitative personal information, researchers from various disciplines contribute to developing methods for extracting data from OSNs. However, there is limited research which addresses extracting data automatically. To the best of the author's knowledge, there is no research which …
-
On the construction, dimensionality, and decoding of linear block code trellises
… we consider near-ML decoding using partial searches of a code trellis or tree. Despite the fact that this approach is suboptimal in terms of the probability of error, it has the potential for an improved trade-off between coding gain and computational effort. The decoding problem faced by a …
-
SCALABLE GRAPH REPRESENTATIONAL LEARNING ALGORITHMS FOR NETWORK MEDICINE
… To deal with this open problem, the first contribution of this thesis is the design and development of the GRAPE (Graph Processing and Embedding) resource for GRL, able to scale with big graphs thanks to specialized and innovative data structures and algorithms efficiently implemented …