Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Institution
- Keyword
-
- Art (1)
- Art vectorization (1)
- Bezier Curves (1)
- Bipartite Independent Set query (1)
- Causal Inference (1)
-
- Causal discovery (1)
- Circuit satisfiability (1)
- Combinatorial game (1)
- Combinatorics (1)
- Computer Science (1)
- Consolidation (1)
- Counting graph embeddings (1)
- Curves (1)
- Even functionals (1)
- Experimental Design (1)
- Graph coloring (1)
- Graph theory (1)
- Graphics (1)
- Intervention (1)
- Knapsack (1)
- Linear algebra (1)
- Mathematics (1)
- Parameterization (1)
- Polygons Mimetic Methods CFD incompressible Fluids (1)
- Polynomial hierarchy (1)
- Raster (1)
- StrokeStrip (1)
- Sub-linear graph algorithms (1)
- Subset sum (1)
- Unbounded subset sum (1)
Articles 1 - 6 of 6
Full-Text Articles in Discrete Mathematics and Combinatorics
Combinatorial Algorithms For Graph Discovery And Experimental Design, Raghavendra K. Addanki
Combinatorial Algorithms For Graph Discovery And Experimental Design, Raghavendra K. Addanki
Doctoral Dissertations
In this thesis, we study the design and analysis of algorithms for discovering the structure and properties of an unknown graph, with applications in two different domains: causal inference and sublinear graph algorithms. In both these domains, graph discovery is possible using restricted forms of experiments, and our objective is to design low-cost experiments. First, we describe efficient experimental approaches to the causal discovery problem, which in its simplest form, asks us to identify the causal relations (edges of the unknown graph) between variables (vertices of the unknown graph) of a given system. For causal discovery, we study algorithms β¦
Moving Polygon Methods For Incompressible Fluid Dynamics, Chris Chartrand
Moving Polygon Methods For Incompressible Fluid Dynamics, Chris Chartrand
Doctoral Dissertations
Hybrid particle-mesh numerical approaches are proposed to solve incompressible fluid flows. The methods discussed in this work consist of a collection of particles each wrapped in their own polygon mesh cell, which then move through the domain as the flow evolves. Variables such as pressure, velocity, mass, and momentum are located either on the mesh or on the particles themselves, depending on the specific algorithm described, and each will be shown to have its own advantages and disadvantages. This work explores what is required to obtain local conservation of mass, momentum, and convergence for the velocity and pressure in a β¦
Games For One, Games For Two: Computationally Complex Fun For Polynomial-Hierarchical Families, Kye Shi
Games For One, Games For Two: Computationally Complex Fun For Polynomial-Hierarchical Families, Kye Shi
HMC Senior Theses
In the first half of this thesis, we explore the polynomial-time hierarchy, emphasizing an intuitive perspective that associates decision problems in the polynomial hierarchy to combinatorial games with fixed numbers of turns. Specifically, problems in π are thought of as 0-turn games, ππ as 1-turn βpuzzleβ games, and in general πΊβπ as π-turn games, in which decision problems answer the binary question, βcan the starting player guarantee a win?β We introduce the formalisms of the polynomial hierarchy through this perspective, alongside definitions of π-turn CIRCUIT SATISFIABILITY games, whose πΊβπ-completeness is assumed from prior work (we briefly justify this assumption β¦
Stroke Clustering And Fitting In Vector Art, Khandokar Shakib
Stroke Clustering And Fitting In Vector Art, Khandokar Shakib
Senior Independent Study Theses
Vectorization of art involves turning free-hand drawings into vector graphics that can be further scaled and manipulated. In this paper, we explore the concept of vectorization of line drawings and study multiple approaches that attempt to achieve this in the most accurate way possible. We utilize a software called StrokeStrip to discuss the different mathematics behind the parameterization and fitting involved in the drawings.
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 β¦
Lasso: Listing All Subset Sums Obediently For Evaluating Unbounded Subset Sums, Christopher N. Burgoyne, Travis J. Wheeler
Lasso: Listing All Subset Sums Obediently For Evaluating Unbounded Subset Sums, Christopher N. Burgoyne, Travis J. Wheeler
Graduate Student Theses, Dissertations, & Professional Papers
In this study we present a novel algorithm, LASSO, for solving the unbounded and bounded subset sum problem. The LASSO algorithm was designed to solve the unbounded SSP quickly and to return all subsets summing to a target sum. As speed was the highest priority, we benchmarked the run time performance of LASSO against implementations of some common approaches to the bounded SSP, as well as the only comparable implementation for solving the unbounded SSP that we could find. In solving the bounded SSP, our algorithm had a significantly faster run time than the competing algorithms when the target sum β¦