Discrete Mathematics and Combinatorics Commons^™

Largest 2-Regular Subgraphs In Complete S-Partite Graphs, Yiyang Jiang

McKelvey School of Engineering Graduate Student Theses & Dissertations

In this thesis, we focus on the class of complete $S$-partite graphs, for $S$ an undirected graph possibly with self-loops, and address the problem of finding largest $2$-regular subgraphs of these graphs, which can be formulated as an integer linear program. Roughly speaking, a complete $S$-partite graph is obtained by replacing every single node of $S$ with a number of nodes, preserving the edge/non-edge relations of $S$. Our motivation in studying largest $2$-regular subgraphs is rooted in the structural systems theory, particularly in the problem of finding largest subnetworks that can sustain controllability or asymptotic stability of the corresponding subsystems. …

A New Approach To Generate Combinatorial Patterns In Logical Analysis Of Data And Its Application To Predict College Retention, Salihah Ahmed E. Jaafari

Theses and Dissertations

Student retention and degree completion remain central challenges for higher-education institutions, with significant implications for student success, institutional effectiveness, and public accountability. While advances in predictive analytics have enabled earlier identification of students at risk of withdrawal, many commonly used machine learning approaches suffer from limited interpretability, constraining their practical usefulness for advising, intervention, and policy decision making. This dissertation addresses the problem of predicting student persistence by developing and evaluating optimization based, interpretable classification models within the Logical Analysis of Data (LAD) framework. Building on existing LAD formulations, this research introduces two novel pattern generation models, the Best Term …

On The Extreme Complexity Of Certain Nearly Regular Graphs, Gregory P. Constantine, Gregory C. Magda

Theory & Applications of Graphs

The complexity of a graph is the number of its labeled spanning trees. It is demonstrated that the seven known triangle-free strongly regular graphs are graphs of maximal complexity among all graphs of the same order and degree; their complements are shown to be of minimal complexity. A generalization to nearly regular graphs with two distinct eigenvalues of the Laplacian is presented. Conjectures and applications of these results to biological problems on neuronal activity are described.

Demystifying Hardware Formal Verification For Undergraduate Education: A Risc-V Processor Case Study With Coursework Implementation, Riley A. Peters

Master's Theses

Hardware verification engineers apply formal methods to prove that a digital device always behaves according to its specification. This differs from traditional functional verification, in which engineers establish correctness by repeatedly sending test inputs to the device and comparing the outputs against a reference model. With the growing complexity of integrated circuits, the demand for digital verification engineers with formal methods experience has continued to increase. However, California Polytechnic State University: San Luis Obispo's current curriculum lacks dedicated material to prepare students for these roles.

This thesis seeks to address the lack of formal methods material through two efforts. First, …

Robust Spacecraft Autonomy For Deep Space Exploration In Special Euclidean Group Se(3), Matthew Wittal

Doctoral Dissertations and Master's Theses

Over the past half-century, humanity has gained extensive experience conducting manned spaceflight near Earth. Arguably, "near Earth" could even include the Moon — the most distant destination humans have reached. However, "near" in this work primarily refers low Earth orbit (LEO). One could argue that we have not truly left Earth since the Apollo, as spacecraft in some LEOs remain subject to atmospheric drag thus emphasizing their continued connection to Earth's immediate environment. Reflecting on this, it becomes clear that humanity has largely remained bound to Earth’s immediate vicinity since the Apollo missions reached the Moon. However, that is set …

Computational Representation, Analysis And Verification Of Requirements In Engineering Design And Systems Engineering, Chandan Kumar Sahu

All Dissertations

Systems are developed to satisfy a set of requirements derived from stakeholders’ needs, defining the problem space for which the system is created as a feasible solution. The system design process begins with eliciting these requirements and concludes with validating whether the created system meets them. Requirements engineering (RE) encompasses elicitation, representation, analysis, documentation, verification, and validation. However, challenges in RE, such as imprecision in natural language (NL), proprietary restrictions, and a lack of standardized quality metrics, hinder the creation of well-formed and comprehensive requirements. These challenges complicate formalization and analysis of requirements.

This dissertation addresses these challenges by proposing …

Decision-Making In Diagnosing Heart Failure Problems Using Dual Hesitant Fuzzy Sets, Manar Mohamed Omran, Reham Abdel-Aziz Abo-Khadra

Journal of Engineering Research

In recent decades, several types of sets, such as fuzzy sets, interval-valued fuzzy sets, intuitionistic fuzzy sets, interval-valued intuitionistic fuzzy sets, type 2 fuzzy sets, type n fuzzy sets, and hesitant fuzzy sets, have been introduced and investigated widely. In this paper, we propose dual hesitant fuzzy sets (DHFSs), which encompass fuzzy sets, intuitionistic fuzzy sets, hesitant fuzzy sets, and fuzzy multi-sets as special cases. Then we investigate the basic operations and properties of DHFSs. We also discuss the relationships among the sets mentioned above, and then propose an extension principle of DHFSs. Additionally, we give an example to illustrate …

Reducing Food Scarcity: The Benefits Of Urban Farming, S.A. Claudell, Emilio Mejia

Journal of Nonprofit Innovation

Urban farming can enhance the lives of communities and help reduce food scarcity. This paper presents a conceptual prototype of an efficient urban farming community that can be scaled for a single apartment building or an entire community across all global geoeconomics regions, including densely populated cities and rural, developing towns and communities. When deployed in coordination with smart crop choices, local farm support, and efficient transportation then the result isn’t just sustainability, but also increasing fresh produce accessibility, optimizing nutritional value, eliminating the use of ‘forever chemicals’, reducing transportation costs, and fostering global environmental benefits.

Imagine Doris, who is …

The Sensitivity Of A Laplacian Family Of Ranking Methods, Claire S. Chang

HMC Senior Theses

Ranking from pairwise comparisons is a particularly rich subset of ranking problems. In this work, we focus on a family of ranking methods for pairwise comparisons which encompasses the well-known Massey, Colley, and Markov methods. We will accomplish two objectives to deepen our understanding of this family. First, we will consider its network diffusion interpretation. Second, we will analyze its sensitivity by studying the "maximal upset" where the direction of an arc between the highest and lowest ranked alternatives is flipped. Through these analyses, we will build intuition to answer the question "What are the characteristics of robust ranking methods?" …

On Communication For Distributed Babai Point Computation, Maiara F. Bollauf, Vinay A. Vaishampayan, Sueli I.R. Costa

Publications and Research

We present a communication-efficient distributed protocol for computing the Babai point, an approximate nearest point for a random vector X∈Rn in a given lattice. We show that the protocol is optimal in the sense that it minimizes the sum rate when the components of X are mutually independent. We then investigate the error probability, i.e. the probability that the Babai point does not coincide with the nearest lattice point, motivated by the fact that for some cases, a distributed algorithm for finding the Babai point is sufficient for finding the nearest lattice point itself. Two different probability models for X …

An Enumeration Of Nested Networks, Nathan Cornelius

Williams Honors College, Honors Research Projects

Nested networks have several applications in phylogenetics and electrical circuit theory. In many cases, there may exist more than one distinct network which correctly models a given data set. This proposes a combinatorial problem to determine all possible network solutions. In this paper, we partially solve this problem by developing exponential generating functions which enumerate all 1-nested and 2-nested unicyclic networks. We also describe our procedure to directly count all 1-nested and 2-nested networks and provide all 1-nested networks with 7, 8, and 9 terminal nodes.

Target Control Of Networked Systems, Isaac S. Klickstein

Mechanical Engineering ETDs

The control of complex networks is an emerging field yet it has already garnered interest from across the scientific disciplines, from robotics to sociology. It has quickly been noticed that many of the classical techniques from controls engineering, while applicable, are not as illuminating as they were for single systems of relatively small dimension. Instead, properties borrowed from graph theory provide equivalent but more practical conditions to guarantee controllability, reachability, observability, and other typical properties of interest to the controls engineer when dealing with large networked systems. This manuscript covers three topics investigated in detail by the author: (i) the …

Controllability And Observability Of The Discrete Fractional Linear State-Space Model, Duc M. Nguyen

Masters Theses & Specialist Projects

This thesis aims to investigate the controllability and observability of the discrete fractional linear time-invariant state-space model. First, we will establish key concepts and properties which are the tools necessary for our task. In the third chapter, we will discuss the discrete state-space model and set up the criteria for these two properties. Then, in the fourth chapter, we will attempt to apply these criteria to the discrete fractional model. The general flow of our objectives is as follows: we start with the first-order linear difference equation, move on to the discrete system, then the fractional difference equation, and finally …

Policy-Preferred Paths In As-Level Internet Topology Graphs, Mehmet Engin Tozal

Theory & Applications of Graphs

Using Autonomous System (AS) level Internet topology maps to determine accurate AS-level paths is essential for network diagnostics, performance optimization, security enforcement, business policy management and topology-aware application development. One significant drawback that we have observed in many studies is simplifying the AS-level topology map of the Internet to an undirected graph, and then using the hop distance as a means to find the shortest paths between the ASes. A less significant drawback is restricting the shortest paths to only valley-free paths. Both approaches usually inflate the number of paths between ASes; introduce erroneous paths that do not conform to …

A High Quality, Eulerian 3d Fluid Solver In C++, Lejon Anthony Mcgowan

Computer Science and Software Engineering

Fluids are a part of everyday life, yet are one of the hardest elements to properly render in computer graphics. Water is the most obvious entity when thinking of what a fluid simulation can achieve (and it is indeed the focus of this project), but many other aspects of nature, like fog, clouds, and particle effects. Real-time graphics like video games employ many heuristics to approximate these effects, but large-scale renderers aim to simulate these effects as closely as possible.

In this project, I wish to achieve effects of the latter nature. Using the Eulerian technique of discrete grids, I …

Ns-K-Nn: Neutrosophic Set-Based K-Nearest Neighbors Classifier, Florentin Smarandache, Yaman Akbulut, Abdulkadir Sengur, Yanhui Guo

Branch Mathematics and Statistics Faculty and Staff Publications

k-nearest neighbors (k-NN), which is known to be a simple and efficient approach, is a non-parametric supervised classifier. It aims to determine the class label of an unknown sample by its k-nearest neighbors that are stored in a training set. The k-nearest neighbors are determined based on some distance functions. Although k-NN produces successful results, there have been some extensions for improving its precision. The neutrosophic set (NS) defines three memberships namely T, I and F. T, I, and F shows the truth membership degree, the false membership degree, and the indeterminacy membership degree, respectively. In this paper, the NS …

Generalized Interval Valued Neutrosophic Graphs Of First Type, Florentin Smarandache, Said Broumi, Mohamed Talea, Assia Bakali, Ali Hassan

Branch Mathematics and Statistics Faculty and Staff Publications

In this paper, motivated by the notion of generalized single valued neutrosophic graphs of first type, we defined a new neutrosophic graphs named generalized interval valued neutrosophic graphs of first type (GIVNG1) and presented a matrix representation for it and studied few properties of this new concept. The concept of GIVNG1 is an extension of generalized fuzzy graphs (GFG1) and generalized single valued neutrosophic of first type (GSVNG1).

Characterizing Forced Communication In Networks, Samuel C. Gutekunst

HMC Senior Theses

This thesis studies a problem that has been proposed as a novel way to disrupt communication networks: the load maximization problem. The load on a member of a network represents the amount of communication that the member is forced to be involved in. By maximizing the load on an important member of the network, we hope to increase that member's visibility and susceptibility to capture. In this thesis we characterize load as a combinatorial property of graphs and expose possible connections between load and spectral graph theory. We specifically describe the load and how it changes in several canonical classes …

Distance In Matrices And Their Applications To Fuzzy Models And Neutrosophic Models, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors for the first time introduce the notion of distance between any two m  n matrices. If the distance is 0 or m  n there is nothing interesting. When the distance happens to be a value t; 0 < t < m  n the study is both innovating and interesting. The three cases of study which is carried out in this book are 1. If the difference between two square matrices is large, will it imply the eigen values and eigen vectors of those matrices are distinct? Several open conjectures in this direction are given. 2. The difference between parity check matrix and the generator matrix for the same C(n, k) code is studied. This will help in detecting errors in storage systems as well as in cryptography.

Generating Minimal T-Wise Test Suites, Luis C. Gutierrez, Carlos Nieto, Francisco Zapata, Martine Ceberio

COURI Symposium Abstracts, Summer 2012

As the use of computing devices increases every day, users rely on the adequate functioning of software. When software is not tested properly, it can yield erroneous information or a complete failure of the system. The NIST estimates that defective software cost the United States economy close to $60 billion a year. Therefore, there is a need to develop software testing techniques that are time and cost effective. Fully testing software under all possible combinations of parameters values cannot be reduced. However, testing can focus on covering all combinations of subsets of parameters and empirical data shows that doing so …

Generating Minimal Pair-Wise Covering Test Suites, Luis C. Gutierrez ^, Martine Ceberio *

COURI Symposium Abstracts, Spring 2012

Software is ubiquitous and needs to be reliable. Software testing therefore plays an important role in software development. Proper testing a software system informs about its quality and reliability so as to prevent unexpected behavior during system execution. One of the methods to prevent failures consists in testing a system under different input values, but when all possible input values are tested, an impractical number of test cases might result. In software testing, pair-wise testing is a combinatorial technique which uses combination of pair input values to generate test cases. Using pair-wise testing dramatically reduces the number of test cases, …

A Group Theoretic Tabu Search Approach To The Traveling Salesman Problem, Shane N. Hall

Theses and Dissertations

The traveling salesman problem (TSP) is a combinatorial optimization problem that is mathematically modeled as a binary integer program. The TSP is a very important problem for the operations research academician and practitioner. This research demonstrates a Group Theoretic Tabu Search (GTTS) Java algorithm for the TSP. The tabu search metaheuristic continuously finds near-optimal solutions to the TSP under various different implementations. Algebraic group theory offers a more formal mathematical setting to study the TSP providing a theoretical foundation for describing tabu search. Specifically, this thesis uses the Symmetric Group on n letters, S(n), which is the set of all …

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer

Mathematical Sciences Technical Reports (MSTR)

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP­ complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, …