Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 7 of 7
Full-Text Articles in Entire DC Network
Fine-Grained Lower Bounds For Problems On Strings And Graphs, Gary Thomas Hoppenworth
Fine-Grained Lower Bounds For Problems On Strings And Graphs, Gary Thomas Hoppenworth
Honors Undergraduate Theses
The motivation of this thesis is to present new lower bounds for important computational problems on strings and graphs, conditioned on plausible conjectures in theoretical computer science. These lower bounds, called conditional lower bounds, are a topic of immense interest in the field of fine-grained complexity, which aims to develop a better understanding of the hardness of problems that can be solved in polynomial time. In this thesis, we give new conditional lower bounds for four interesting computational problems: the median and center string edit distance problems, the pattern matching on labeled graphs problem, and the subtree isomorphism problem. These …
Modeling User Transportation Patterns Using Mobile Devices, Erfan Davami
Modeling User Transportation Patterns Using Mobile Devices, Erfan Davami
Electronic Theses and Dissertations
Participatory sensing frameworks use humans and their computing devices as a large mobile sensing network. Dramatic accessibility and affordability have turned mobile devices (smartphone and tablet computers) into the most popular computational machines in the world, exceeding laptops. By the end of 2013, more than 1.5 billion people on earth will have a smartphone. Increased coverage and higher speeds of cellular networks have given these devices the power to constantly stream large amounts of data. Most mobile devices are equipped with advanced sensors such as GPS, cameras, and microphones. This expansion of smartphone numbers and power has created a sensing …
Computational Methods For Comparative Non-Coding Rna Analysis: From Structural Motif Identification To Genome-Wide Functional Classification, Cuncong Zhong
Electronic Theses and Dissertations
Recent advances in biological research point out that many ribonucleic acids (RNAs) are transcribed from the genome to perform a variety of cellular functions, rather than merely acting as information carriers for protein synthesis. These RNAs are usually referred to as the non-coding RNAs (ncRNAs). The versatile regulation mechanisms and functionalities of the ncRNAs contribute to the amazing complexity of the biological system. The ncRNAs perform their biological functions by folding into specific structures. In this case, the comparative study of the ncRNA structures is key to the inference of their molecular and cellular functions. We are especially interested in …
Algorithms For Community Identification In Complex Networks, Mahadevan Vasudevan
Algorithms For Community Identification In Complex Networks, Mahadevan Vasudevan
Electronic Theses and Dissertations
First and foremost, I would like to extend my deepest gratitude to my advisor, Professor Narsingh Deo, for his excellent guidance and encouragement, and also for introducing me to this wonderful science of complex networks. Without his support this dissertation would not have been possible. I would also like to thank the members of my research committee, professors Charles Hughes, Ratan Guha, Mainak Chatterjee and Yue Zhao for their advice and guidance during the entire process. I am indebted to the faculty and the staff of the Department of Electrical Engineering and Computer Science for providing me the resources and …
Convergence Of The Mean Shift Algorithm And Its Generalizations, Ting Hu
Convergence Of The Mean Shift Algorithm And Its Generalizations, Ting Hu
Electronic Theses and Dissertations
Mean shift is an effective iterative algorithm widely used in image analysis tasks like tracking, image segmentation, smoothing, filtering, edge detection and etc. It iteratively estimates the modes of the probability function of a set of sample data points based in a region. Mean shift was invented in 1975, but it was not widely used until the work by Cheng in 1995. After that, it becomes popular in computer vision. However the convergence, a key character of any iterative algorithm, has been rigorously proved only very recently, but with strong assumptions. In this thesis, the method of mean shift is …
Alliances In Graphs: Parameterized Algorithms And On Partitioning Series-Parallel Graphs, Rosa Enciso
Alliances In Graphs: Parameterized Algorithms And On Partitioning Series-Parallel Graphs, Rosa Enciso
Electronic Theses and Dissertations
Alliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G = (V, E) is a non empty set S ⊆ V where, for all x ∈ S, |N[x] ∩ S| ≥ |N[x] − S|. Consequently, every vertex that is a member of a defensive alliance has at least as many vertices defending it as there are vertices attacking it. Alliances can …
Dynamic Shared State Maintenance In Distributed Virtual Environments, Felix George Hamza-Lup
Dynamic Shared State Maintenance In Distributed Virtual Environments, Felix George Hamza-Lup
Electronic Theses and Dissertations
Advances in computer networks and rendering systems facilitate the creation of distributed collaborative environments in which the distribution of information at remote locations allows efficient communication. Particularly challenging are distributed interactive Virtual Environments (VE) that allow knowledge sharing through 3D information. In a distributed interactive VE the dynamic shared state represents the changing information that multiple machines must maintain about the shared virtual components. One of the challenges in such environments is maintaining a consistent view of the dynamic shared state in the presence of inevitable network latency and jitter. A consistent view of the shared scene will significantly increase …