Open Access. Powered by Scholars. Published by Universities.®
- Discipline
-
- Mathematics (9)
- Other Computer Sciences (8)
- Discrete Mathematics and Combinatorics (7)
- Databases and Information Systems (6)
- OS and Networks (6)
-
- Numerical Analysis and Scientific Computing (4)
- Applied Mathematics (2)
- Engineering (2)
- Other Applied Mathematics (2)
- Systems Architecture (2)
- Algebra (1)
- Artificial Intelligence and Robotics (1)
- Computational Biology (1)
- Data Science (1)
- Education (1)
- Electrical and Computer Engineering (1)
- Genetics and Genomics (1)
- Information Security (1)
- Life Sciences (1)
- Operations Research, Systems Engineering and Industrial Engineering (1)
- Other Mathematics (1)
- Programming Languages and Compilers (1)
- Science and Mathematics Education (1)
- Statistics and Probability (1)
- Systems Biology (1)
- Institution
-
- Singapore Management University (4)
- University of Dayton (4)
- Old Dominion University (3)
- Selected Works (2)
- City University of New York (CUNY) (1)
-
- Claremont Colleges (1)
- Coastal Carolina University (1)
- Dartmouth College (1)
- East Tennessee State University (1)
- Georgia Southern University (1)
- Louisiana State University (1)
- New Jersey Institute of Technology (1)
- Portland State University (1)
- Trinity College (1)
- University of Kentucky (1)
- University of Nebraska - Lincoln (1)
- University of Tennessee, Knoxville (1)
- Ursinus College (1)
- Virginia Commonwealth University (1)
- Wilfrid Laurier University (1)
- Publication Year
- Publication
-
- Computer Science Faculty Publications (5)
- Research Collection School Of Computing and Information Systems (4)
- Computer Science Theses & Dissertations (2)
- Zhongmei Yao (2)
- All HMC Faculty Publications and Research (1)
-
- Computer Science Honors Papers (1)
- Dartmouth Scholarship (1)
- Department of Mathematics: Dissertations, Theses, and Student Research (1)
- Dissertations and Theses (1)
- Dissertations, Theses, and Capstone Projects (1)
- Doctoral Dissertations (1)
- Electronic Theses and Dissertations (1)
- Honors College Theses (1)
- Honors Theses (1)
- LSU Master's Theses (1)
- Senior Theses and Projects (1)
- Theses (1)
- Theses and Dissertations (1)
- Theses and Dissertations (Comprehensive) (1)
- Theses and Dissertations--Computer Science (1)
- Publication Type
Articles 1 - 29 of 29
Full-Text Articles in Theory and Algorithms
A Survey On Online Matching And Ad Allocation, Ryan Lee
A Survey On Online Matching And Ad Allocation, Ryan Lee
Theses
One of the classical problems in graph theory is matching. Given an undirected graph, find a matching which is a set of edges without common vertices. In 1990s, Richard Karp, Umesh Vazirani, and Vijay Vazirani would be the first computer scientists to use matchings for online algorithms [8]. In our domain, an online algorithm operates in the online setting where a bipartite graph is given. On one side of the graph there is a set of advertisers and on the other side we have a set of impressions. During the online phase, multiple impressions will arrive and the objective of …
Matrix Interpretations And Tools For Investigating Even Functionals, Benjamin Stringer
Matrix Interpretations And Tools For Investigating Even Functionals, Benjamin Stringer
Theses and Dissertations--Computer Science
Even functionals are a set of polynomials evaluated on the terms of hollow symmetric matrices. Their properties lend themselves to applications such as counting subgraph embeddings in generic (weighted or unweighted) host graphs and computing moments of binary quadratic forms, which occur in combinatorial optimization. This research focuses primarily on counting subgraph embeddings, which is traditionally accomplished with brute-force algorithms or algorithms curated for special types of graphs. Even functionals provide a method for counting subgraphs algebraically in time proportional to matrix multiplication and is not restricted to particular graph types. Counting subgraph embeddings can be accomplished by evaluating a …
Quantum Grover's Oracles With Symmetry Boolean Functions, Peng Gao
Quantum Grover's Oracles With Symmetry Boolean Functions, Peng Gao
Dissertations and Theses
Quantum computing has become an important research field of computer science and engineering. Among many quantum algorithms, Grover's algorithm is one of the most famous ones. Designing an effective quantum oracle poses a challenging conundrum in circuit and system-level design for practical application realization of Grover's algorithm.
In this dissertation, we present a new method to build quantum oracles for Grover's algorithm to solve graph theory problems. We explore generalized Boolean symmetric functions with lattice diagrams to develop a low quantum cost and area efficient quantum oracle. We study two graph theory problems: cycle detection of undirected graphs and generalized …
Dijkstra’S Pathfinder, Taylor F. Malamut
Dijkstra’S Pathfinder, Taylor F. Malamut
Honors Theses
Dijkstra’s algorithm has been widely studied and applied since it was first published in 1959. This research shows that Dijkstra’s algorithm can be used to find the shortest path between two stations on the Washington D.C. Metro. After exploring different types of research and applying Dijkstra’s algorithm, it was found that the algorithm will always yield the shortest path, even if visually a shorter path was initially expected.
Evaluation Of Algorithms For Randomizing Key Item Locations In Game Worlds, Caleb Johnson
Evaluation Of Algorithms For Randomizing Key Item Locations In Game Worlds, Caleb Johnson
LSU Master's Theses
In the past few years, game randomizers have become increasingly popular. In general, a game randomizer takes some aspect of a game that is usually static and shuffles it somehow. In particular, in this paper we will discuss the type of randomizer that shuffles the locations of items in a game where certain key items are needed to traverse the game world and access some of these locations. Examples of these types of games include series such as The Legend of Zelda and Metroid.
In order to accomplish this shuffling in such a way that the player is able to …
Separability And Vertex Ordering Of Graphs, Elizabeth Gorbonos
Separability And Vertex Ordering Of Graphs, Elizabeth Gorbonos
Theses and Dissertations (Comprehensive)
Many graph optimization problems, such as finding an optimal coloring, or a largest clique, can be solved by a divide-and-conquer approach. One such well-known technique is decomposition by clique separators where a graph is decomposed into special induced subgraphs along their clique separators. While the most common practice of this method employs minimal clique separators, in this work we study other variations as well. We strive to characterize their structure and in particular the bound on the number of atoms. In fact, we strengthen the known bounds for the general clique cutset decomposition and the minimal clique separator decomposition. Graph …
Approximation Algorithms For Effective Team Formation, George Rabanca
Approximation Algorithms For Effective Team Formation, George Rabanca
Dissertations, Theses, and Capstone Projects
This dissertation investigates the problem of creating multiple disjoint teams of maximum efficacy from a fixed set of workers. We identify three parameters which directly correlate to the team effectiveness — team expertise, team cohesion and team size — and propose efficient algorithms for optimizing each in various settings. We show that under standard assumptions the problems we explore are not optimally solvable in polynomial time, and thus we focus on developing efficient algorithms with guaranteed worst case approximation bounds. First, we investigate maximizing team expertise in a setting where each worker has different expertise for each job and each …
Network Modeling Of Infectious Disease: Transmission, Control And Prevention, Christina M. Chandler
Network Modeling Of Infectious Disease: Transmission, Control And Prevention, Christina M. Chandler
Honors College Theses
Many factors come into play when it comes to the transmission of infectious diseases. In disease control and prevention, it is inevitable to consider the general population and the relationships between individuals as a whole, which calls for advanced mathematical modeling approaches.
We will use the concept of network flow and the modified Ford-Fulkerson algorithm to demonstrate the transmission of infectious diseases over a given period of time. Through our model one can observe what possible measures should be taken or improved upon in the case of an epidemic. We identify key nodes and edges in the resulted network, which …
Network Analytics For The Mirna Regulome And Mirna-Disease Interactions, Joseph Jayakar Nalluri
Network Analytics For The Mirna Regulome And Mirna-Disease Interactions, Joseph Jayakar Nalluri
Theses and Dissertations
miRNAs are non-coding RNAs of approx. 22 nucleotides in length that inhibit gene expression at the post-transcriptional level. By virtue of this gene regulation mechanism, miRNAs play a critical role in several biological processes and patho-physiological conditions, including cancers. miRNA behavior is a result of a multi-level complex interaction network involving miRNA-mRNA, TF-miRNA-gene, and miRNA-chemical interactions; hence the precise patterns through which a miRNA regulates a certain disease(s) are still elusive. Herein, I have developed an integrative genomics methods/pipeline to (i) build a miRNA regulomics and data analytics repository, (ii) create/model these interactions into networks and use optimization techniques, motif …
Shortest Path Based Decision Making Using Probabilistic Inference, Akshat Kumar
Shortest Path Based Decision Making Using Probabilistic Inference, Akshat Kumar
Research Collection School Of Computing and Information Systems
We present a new perspective on the classical shortest path routing (SPR) problem in graphs. We show that the SPR problem can be recast to that of probabilistic inference in a mixture of simple Bayesian networks. Maximizing the likelihood in this mixture becomes equivalent to solving the SPR problem. We develop the well known Expectation-Maximization (EM) algorithm for the SPR problem that maximizes the likelihood, and show that it does not get stuck in a locally optimal solution. Using the same probabilistic framework, we then address an NP-Hard network design problem where the goal is to repair a network of …
The Apprentices' Tower Of Hanoi, Cory Bh Ball
The Apprentices' Tower Of Hanoi, Cory Bh Ball
Electronic Theses and Dissertations
The Apprentices' Tower of Hanoi is introduced in this thesis. Several bounds are found in regards to optimal algorithms which solve the puzzle. Graph theoretic properties of the associated state graphs are explored. A brief summary of other Tower of Hanoi variants is also presented.
Positive Influence Dominating Set Generation Via A New Greedy Algorithm, Matthew Rink
Positive Influence Dominating Set Generation Via A New Greedy Algorithm, Matthew Rink
Computer Science Honors Papers
Current algorithms in the Positive Influence Dominating Set (PIDS) problem domain are focused on a specific type of PIDS, the Total Positive Influence Dominating Set (TPIDS). We have developed an algorithm specifically targeted towards the non-total type of PIDS. In addition to our new algorithm, we adapted two existing TPIDS algorithms to generate PIDS. We ran simulations for all three algorithms, and our new algorithm consistently generates smaller PIDS than either existing algorithm, with our algorithm generating PIDS approximately 5% smaller than the better of the two existing algorithms.
On Node Isolation Under Churn In Unstructured P2p Networks With Heavy-Tailed Lifetimes, Zhongmei Yao, Xiaoming Wang, Dmitri Loguinov
On Node Isolation Under Churn In Unstructured P2p Networks With Heavy-Tailed Lifetimes, Zhongmei Yao, Xiaoming Wang, Dmitri Loguinov
Zhongmei Yao
Previous analytical studies [12], [18] of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces the probability of user isolation and graph partitioning compared to uniform selection of neighbors. In fact, the second strategy based on random walks on age-weighted graphs demonstrates that for lifetimes with infinite variance, the system …
Node Isolation Model And Age-Based Neighbor Selection In Unstructured P2p Networks, Zhongmei Yao, Derek Leonard, Dmitri Loguinov
Node Isolation Model And Age-Based Neighbor Selection In Unstructured P2p Networks, Zhongmei Yao, Derek Leonard, Dmitri Loguinov
Zhongmei Yao
Previous analytical studies of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces the probability of user isolation and graph partitioning compared with uniform selection of neighbors. In fact, the second strategy based on random walks on age-proportional graphs demonstrates that, for lifetimes with infinite variance, the system monotonically increases …
Verifying Monadic Second-Order Properties Of Graph Programs, Christopher M. Poskitt, Detlef Plump
Verifying Monadic Second-Order Properties Of Graph Programs, Christopher M. Poskitt, Detlef Plump
Research Collection School Of Computing and Information Systems
The core challenge in a Hoare- or Dijkstra-style proof system for graph programs is in defining a weakest liberal precondition construction with respect to a rule and a postcondition. Previous work addressing this has focused on assertion languages for first-order properties, which are unable to express important global properties of graphs such as acyclicity, connectedness, or existence of paths. In this paper, we extend the nested graph conditions of Habel, Pennemann, and Rensink to make them equivalently expressive to monadic second-order logic on graphs. We present a weakest liberal precondition construction for these assertions, and demonstrate its use in verifying …
Construction Algorithms For Expander Graphs, Vlad S. Burca
Construction Algorithms For Expander Graphs, Vlad S. Burca
Senior Theses and Projects
Graphs are mathematical objects that are comprised of nodes and edges that connect them. In computer science they are used to model concepts that exhibit network behaviors, such as social networks, communication paths or computer networks. In practice, it is desired that these graphs retain two main properties: sparseness and high connectivity. This is equivalent to having relatively short distances between two nodes but with an overall small number of edges. These graphs are called expander graphs and the main motivation behind studying them is the efficient network structure that they can produce due to their properties. We are specifically …
Verifying Total Correctness Of Graph Programs, Christopher M. Poskitt, Detlef Plump
Verifying Total Correctness Of Graph Programs, Christopher M. Poskitt, Detlef Plump
Research Collection School Of Computing and Information Systems
GP 2 is an experimental nondeterministic programming language based on graph transformation rules, allowing for visual programming and the solving of graph problems at a high-level of abstraction. In previous work we demonstrated how to verify graph programs using a Hoare-style proof calculus, but only partial correctness was considered. In this paper, we add new proof rules and termination functions, which allow for proofs to additionally guarantee that program executions always terminate (weak total correctness), or that programs always terminate and do so without failure (total correctness). We show that the new proof rules are sound with respect to the …
Verification Of Graph Programs, Christopher M. Poskitt
Verification Of Graph Programs, Christopher M. Poskitt
Research Collection School Of Computing and Information Systems
GP (for Graph Programs) is an experimental nondeterministic programming language which allows for the manipulation of graphs at a high level of abstraction. The program states of GP are directed labelled graphs. These are manipulated directly via the application of (conditional) rule schemata, which generalise double-pushout rules with expressions over labels and relabelling. In contrast with graph grammars, the application of these rule schemata is directed by a number of simple control constructs including sequential composition, conditionals, and as-long-as-possible iteration. GP shields programmers at all times from low-level implementation issues (e.g. graph representation), and with its nondeterministic semantics, allows one …
Combinatorics Using Computational Methods, Derrick Stolee
Combinatorics Using Computational Methods, Derrick Stolee
Department of Mathematics: Dissertations, Theses, and Student Research
Computational combinatorics involves combining pure mathematics, algorithms, and computational resources to solve problems in pure combinatorics. This thesis provides a theoretical framework for combinatorial search, which is then applied to several problems in combinatorics. Some results in space-bounded computational complexity are also presented.
On Superposition Of Heterogeneous Edge Processes In Dynamic Random Graphs, Zhongmei Yao, Daren B. H. Cline, Dmitri Loguinov
On Superposition Of Heterogeneous Edge Processes In Dynamic Random Graphs, Zhongmei Yao, Daren B. H. Cline, Dmitri Loguinov
Computer Science Faculty Publications
This paper builds a generic modeling framework for analyzing the edge-creation process in dynamic random graphs in which nodes continuously alternate between active and inactive states, which represent churn behavior of modern distributed systems. We prove that despite heterogeneity of node lifetimes, different initial out-degree, non-Poisson arrival/failure dynamics, and complex spatial and temporal dependency among creation of both initial and replacement edges, a superposition of edge-arrival processes to a live node under uniform selection converges to a Poisson process when system size becomes sufficiently large. Due to the convoluted dependency and non-renewal nature of various point processes, this result significantly …
Transcriptomic Data Analysis Using Graph-Based Out-Of-Core Methods, Gary L Rogers
Transcriptomic Data Analysis Using Graph-Based Out-Of-Core Methods, Gary L Rogers
Doctoral Dissertations
Biological data derived from high-throughput microarrays can be transformed into finite, simple, undirected graphs and analyzed using tools first introduced by the Langston Lab at the University of Tennessee. Transforming raw data can be broken down into three main tasks: data normalization, generation of similarity metrics, and threshold selection. The choice of methods used in each of these steps effect the final outcome of the graph, with respect to size, density, and structure. A number of different algorithms are examined and analyzed to illustrate the magnitude of the effects.
Graph-based tools are then used to extract putative gene networks. These …
Algorithms For Vertex-Weighted Matching In Graphs, Mahantesh Halappanavar
Algorithms For Vertex-Weighted Matching In Graphs, Mahantesh Halappanavar
Computer Science Theses & Dissertations
A matching M in a graph is a subset of edges such that no two edges in M are incident on the same vertex. Matching is a fundamental combinatorial problem that has applications in many contexts: high-performance computing, bioinformatics, network switch design, web technologies, etc. Examples in the first context include sparse linear systems of equations, where matchings are used to place large matrix elements on or close to the diagonal, to compute the block triangular decomposition of sparse matrices, to construct sparse bases for the null space or column space of under-determined matrices, and to coarsen graphs in multi-level …
Node Isolation Model And Age-Based Neighbor Selection In Unstructured P2p Networks, Zhongmei Yao, Derek Leonard, Dmitri Loguinov
Node Isolation Model And Age-Based Neighbor Selection In Unstructured P2p Networks, Zhongmei Yao, Derek Leonard, Dmitri Loguinov
Computer Science Faculty Publications
Previous analytical studies of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces the probability of user isolation and graph partitioning compared with uniform selection of neighbors. In fact, the second strategy based on random walks on age-proportional graphs demonstrates that, for lifetimes with infinite variance, the system monotonically increases …
On Node Isolation Under Churn In Unstructured P2p Networks With Heavy-Tailed Lifetimes, Zhongmei Yao, Xiaoming Wang, Dmitri Loguinov
On Node Isolation Under Churn In Unstructured P2p Networks With Heavy-Tailed Lifetimes, Zhongmei Yao, Xiaoming Wang, Dmitri Loguinov
Computer Science Faculty Publications
Previous analytical studies [12], [18] of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces the probability of user isolation and graph partitioning compared to uniform selection of neighbors. In fact, the second strategy based on random walks on age-weighted graphs demonstrates that for lifetimes with infinite variance, the system …
All Minimal Prime Extensions Of Hereditary Classes Of Graphs, Vassilis Giakoumakis, Stephan Olariu
All Minimal Prime Extensions Of Hereditary Classes Of Graphs, Vassilis Giakoumakis, Stephan Olariu
Computer Science Faculty Publications
The substitution composition of two disjoint graphs G1 and G2 is obtained by first removing a vertex x from G2 and then making every vertex in G1 adjacent to all neighbours of x in G2. Let F be a family of graphs defined by a set Z* of forbidden configurations. Giakoumakis [V. Giakoumakis, On the closure of graphs under substitution, Discrete Mathematics 177 (1997) 83–97] proved that F∗, the closure under substitution of F, can be characterized by a set Z∗ of forbidden configurations — the minimal prime extensions of Z. He also …
On Static And Dynamic Partitioning Behavior Of Large-Scale Networks, Derek Leonard, Zhongmei Yao, Xiaoming Wang, Dmitri Loguinov
On Static And Dynamic Partitioning Behavior Of Large-Scale Networks, Derek Leonard, Zhongmei Yao, Xiaoming Wang, Dmitri Loguinov
Computer Science Faculty Publications
In this paper, we analyze the problem of network disconnection in the context of large-scale P2P networks and understand how both static and dynamic patterns of node failure affect the resilience of such graphs. We start by applying classical results from random graph theory to show that a large variety of deterministic and random P2P graphs almost surely (i.e., with probability 1-o(1)) remain connected under random failure if and only if they have no isolated nodes. This simple, yet powerful, result subsequently allows us to derive in closed-form the probability that a P2P network develops isolated nodes, and therefore partitions, …
Low-Degree Spanning Trees Of Small Weight, Samir Khuller, Balaji Raghavachari, Neal Young
Low-Degree Spanning Trees Of Small Weight, Samir Khuller, Balaji Raghavachari, Neal Young
Dartmouth Scholarship
Given n points in the plane, the degree-K spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low-weight degree-K spanning trees for $K > 2$. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree 3 whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of degree 4 whose weight is at most 1.25 times …
Indifference Graphs And The Single Row Routing Problem, Peter J. Looges
Indifference Graphs And The Single Row Routing Problem, Peter J. Looges
Computer Science Theses & Dissertations
This thesis investigates the subclass of interval graphs known as indifference graphs. New optimal algorithms for recognition, center, diameter, maximum matching, Hamiltonian path and domination in indifference graphs are presented. The recognition algorithm produces a linear order with properties which allow the solution of the other problems in linear time. Indifference graphs are further applied to the single row routing problem which results in both sequential,. and parallel routing algorithms.
On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis
On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis
All HMC Faculty Publications and Research
We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with Πk-formulae of size n for which every Σk-formula has size exp Ω(n1/(k-1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a Σk-formula of size exp O(n1/(k-1)). Thus our hierarchy theorem is the best possible.