Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Institution
- Keyword
-
- Bipartite Independent Set query (1)
- Causal Inference (1)
- Causal discovery (1)
- Circuit satisfiability (1)
- Combinatorial game (1)
-
- Combinatorics (1)
- Counting graph embeddings (1)
- Even functionals (1)
- Experimental Design (1)
- Graph coloring (1)
- Graph theory (1)
- Intervention (1)
- Knapsack (1)
- Linear algebra (1)
- Neighbor-distinguishing coloring (1)
- Polynomial hierarchy (1)
- Set coloring (1)
- Sub-linear graph algorithms (1)
- Subset sum (1)
- Total graph (1)
- Unbounded subset sum (1)
- Publication
- Publication Type
Articles 1 - 5 of 5
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 β¦
On The Total Set Chromatic Number Of Graphs, Mark Anthony C. Tolentino, Gerone Russel J. Eugenio, Mari-Jo P. Ruiz
On The Total Set Chromatic Number Of Graphs, Mark Anthony C. Tolentino, Gerone Russel J. Eugenio, Mari-Jo P. Ruiz
Theory and Applications of Graphs
Given a vertex coloring c of a graph, the neighborhood color set of a vertex is defined to be the set of all of its neighborsβ colors. The coloring c is called a set coloring if any two adjacent vertices have different neighborhood color sets. The set chromatic number Οs(G) of a graph G is the minimum number of colors required in a set coloring of G. In this work, we investigate a total analog of set colorings; that is, we study set colorings of the total graph of graphs. Given a graph G = (V, E) β¦
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 β¦
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 β¦