Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 95).

Thesis (M.S.)--West Virginia University, 2003. / Title from document title page. Document formatted into pages; contains iii, 34 p. : ill. Includes abstract. Includes bibliographical references (p. 33-34).

Thesis (Ph. D.)--Lehigh University, 2004. / Includes vita. Includes bibliographical references (leaves 113-118).

Thesis (Ph. D.)--University of Louisville, 2009. / Department of Mathematics. Vita. "May 2009." Includes bibliographical references (leaves 67-69) and index.

Given a complete bipartite graph on two sets of points containing n points each, in a bottleneck matching problem, we want to find an one-to-one correspondence, also called a matching, that minimizes the length of its largest edge; the length of an edge is simply the Euclidean distance between its end-points. As an application, consider matching taxis to requests while minimizing the largest distance between any request to its matched taxi. The length of the largest edge (also called the bottleneck distance) has numerous applications in machine learning as well as topological data analysis. One can use the classical Hopcroft-Karp (HK-) Algorithm to find the bottleneck matching. In this thesis, we consider the case where A and B are points that are generated uniformly at random from a unit square. Instead of the classical HK-Algorithm, we implement and empirically analyze a new algorithm by Lahn and Raghvendra (Symposium on Computational Geometry, 2019). Our experiments show that our approach outperforms the HK-Algorithm based approach for computing bottleneck matching. / Master of Science / Consider the problem of matching taxis to an equal number of requests. While matching them, one objective is to minimize the largest distance between a request and its match. Finding such a matching is called the bottleneck matching problem. In addition, this optimization problem arises in topological data analysis as well as machine learning. In this thesis, I conduct an empirical analysis of a new algorithm, which is called the FAST-MATCH algorithm, to find the bottleneck matching. I find that, when a large input data is randomly generated from a unit square, the FAST-MATCH algorithm performs substantially faster than the classical methods.

Suppose G is a graph with n vertices and m edges. Let n¡¬ be the maximum number of vertices in an induced bipartite subgraph of G and let m¡¬ be the maximum number of edges in a spanning bipartite subgraph of G. Then b(G) = m¡¬/m is called the bipartite density of G, and b∗(G) = n¡¬/n is called the bipartite ratio of G. It is proved in [18] that if G is a 2-connected triangle-free subcubic graph, then apart from seven exceptional graphs, we have b(G) ≥ 17/21. If G is a 2-connected triangle-free subcubic graph, then b∗(G) ≥ 5/7 provided that G is not the Petersen graph and not the dodecahedron. These two results are consequences of a more technical result which is proved by induction: If G is a 2-connected triangle-free subcubic graph with minimum degree 2, then G has an induced bipartite subgraph H with |V (H)| ≥ (5n3 + 6n2 + ǫ(G))/7, where ni = ni(G) are the number of degree i vertices of G, and ǫ(G) ∈ {−2,−1, 0, 1}. To determine ǫ(G), four classes of graphs G1, G2, G3 and F-cycles are onstructed. For G ∈ Gi, we have ǫ(G) = −3 + i and for an F-cycle G, we have ǫ(G) = 0. Otherwise, ǫ(G) = 1. To construct these graph classes, eleven graph operations are used. This thesis studies the structural property of graphs in G1, G2, G3. First of all, a computer algorithm is used to generate all the graphs in Gi for i = 1, 2, 3. Let P be the set of 2-edge connected subcubic triangle-free planar graphs with minimum degree 2. Let G¡¬ 1 be the set of graphs in P with all faces of degree 5, G¡¬2 the set of graphs in P with all faces of degree 5 except that one face has degree 7, and G¡¬3 the set of graphs in P with all faces of degree 5 except that either two faces are of degree 7 or one face is of degree 9. By checking the graphs generated by the computer algorithm, it is easy to see that Gi ⊆ G¡¬i for i = 1, 2, 3. The main results of this thesis are that for i = 1, 2, Gi = G¡¬i and G¡¬3 = G3 ¡åR, where R is a set of nine F-cycles.

This thesis targets at providing an algebraic method to indicate network behaviors. Furthermore, for a signed-average consensus problem of the system behaviors, event-triggering signed-average algorithms are designed to reduce the communication overheads. In Chapter 1, the background is introduced, and the problem is formulated. In Chapter 2, notations and basics of graph theory are presented. It is known that the terminal value of the system state is determined by the initial state, left eigenvector and right eigenvector associated with zero eigenvalue of the Laplacian matrix. Since there is no mathematical expression of right eigenvector, in Chapter 3, mathematical expression of right eigenvector is given. In Chapter 4, algebraic trait for structurally balanced property of a node is proposed. In Chapter 5, a method for characterization of collective behaviors under directed signed networks is developed. In Chapter 6, dynamic event-triggering signed-average algorithms are proposed and proved for the purpose of relieving the communication burden between agents. Chapter 7 summarizes the thesis and gives future directions.

No description available.

Alon 和Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) 證明了如果一個圖是ε -非二部圖，那麼階數為Ỡ(1/ε) 的隨機導出于圖以很大概率是非二部圖。我們進一步猜想，這個導出子圖以很大概率是Ω(ε)-非二部圖。Gonen 和Ron (RANDOM 2007) 證明了當圖的最大度不超過O (εn )時猜想成立。我們將對更一般的情形給出證明，對於任意d，所有d 正則(或幾乎d 正則)的圖猜想成立。 / 假設猜想成立的情況下，我們證明二分屬性是可以被單側誤差在O(1/ε^c ) 時間內檢驗的，其中c 是一個嚴格小於2 的常數，而這個結果也改進了Alon 和Krivelevich 的檢驗算法。由於己知對二分屬性的非適應性的檢驗算法需要Ω(1 /ε²) 的複雜性(Bogdanov 和Trevisan ， CCC 2004) ，我們的結果也得出，假設猜想成立，適應性對檢驗二分屬性是有幫助的。 / 另外一個有很多屬性檢驗問題被廣泛研究的領域是布爾函數。對布爾函數單調性的檢驗也是屬性檢驗的經典問題。給定對布爾函數f: {0,1}{U+207F} → {0,1} 的訪問，在[18]中，證明了檢驗算法複雜性的下界是Ω(√n) 。另一方面，在[21]中，作者們構造了一個複雜性為O(n) 的算法。在本文中，我們刻畫一些單調布爾函數的本質，設計算法并分析其對於一些困難例子的效果。最近，在[14] 中， 一個類似的算法被證明是非適應性，單側誤差，複雜性為Ỡ (n⁵/⁶ ε⁻⁵/³) 的算法。 / Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) show that if a graph is ε-far from bipartite, then the subgraph induced by a random subset of Ỡ (1/ε) vertices is not bipartite with high probability. We conjecture that the induced subgraph is Ω(ε)-far from bipartite with high probability. Gonen and Ron (RANDOM 2007) proved this conjecture in the case when the degrees of all vertices are at most O(εn). We give a more general proof that works for any d-regular (or almost d-regular) graph for arbitrary degree d. / Assuming this conjecture, we prove that bipartiteness is testable with one-sided error in time O(1=ε{U+1D9C}), where c is a constant strictly smaller than two, improving upon the tester of Alon and Krivelevich. As it is known that non-adaptive testers for bipartiteness require Ω(1/ε²) queries (Bogdanov and Trevisan, CCC2004), our result shows, assuming the conjecture, that adaptivity helps in testing bipartiteness. / The other area in which various properties have been well studied is boolean function. Testing monotonicity of Boolean functions is a classical question in property testing. Given oracle access to a Boolean function f : {0, 1}{U+207F} →{0, 1}, in [18], it is shown a lower bound of testing is Ω(√n). On the other hand, in [21], the authors introduced an algorithm to test monotonicity using O(n) queries. In this paper, we characterize some nature of monotone functions, design a tester and analyze the performance on some generalizations of the hard case. Recently, in [14], a similar tester is shown to be a non-adaptive, one-sided error tester making Ỡ (n⁵/⁶ ε⁻⁵/³) queries. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Li, Fan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 76-79). / Abstracts also in Chinese. / Abstract --- p.i / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Property Testing --- p.1 / Chapter 1.2 --- Testing Bipartiteness --- p.4 / Chapter 1.3 --- Testing Monotonicity --- p.7 / Chapter 2 --- Testing Bipartiteness --- p.11 / Chapter 2.1 --- Background --- p.11 / Chapter 2.1.1 --- Our result --- p.11 / Chapter 2.1.2 --- The algorithms of Gonen and Ron --- p.13 / Chapter 2.1.3 --- Our proof --- p.16 / Chapter 2.1.4 --- Notation --- p.19 / Chapter 2.2 --- Splitting the vertices by degree --- p.19 / Chapter 2.3 --- The algorithm for high degree vertices --- p.20 / Chapter 2.4 --- Eliminating the high degree vertices --- p.22 / Chapter 2.5 --- From an XOR game to a bipartite graph --- p.33 / Chapter 2.6 --- Proof of the main theorem --- p.35 / Chapter 2.7 --- Proof of the conjecture for regular graphs --- p.37 / Chapter 3 --- Testing Monotonicity --- p.40 / Chapter 3.1 --- Towards an improved tester --- p.40 / Chapter 3.1.1 --- Properties of Distribution D --- p.42 / Chapter 3.1.2 --- An Alternative Representation of D --- p.46 / Chapter 3.1.3 --- Performance of D on Decreasing Functions --- p.51 / Chapter 3.1.4 --- Functions Containing Ω(2{U+207F}) Disjoint Violating Edges --- p.54 / Chapter 3.2 --- A o(n) Monotonicity Tester [14] and Some Improvements --- p.62 / Chapter 3.2.1 --- A o(n) Monotonicity Tester [14] --- p.62 / Chapter 3.2.2 --- An Alternative Proof of Theorem 3.2.2 --- p.65 / Chapter 4 --- Other Related Results --- p.67 / Chapter 4.1 --- Short Odd Cycles in Graphs that are Far From Bipartiteness --- p.67 / Chapter 4.2 --- Fourier Analysis on Boolean Functions --- p.69 / Bibliography --- p.76

In 1997, Drs. G. R. Blakley and I. Borosh published two papers whose stated purpose was to present a general formulation of the notion of a code that depends only upon a code's structure and not its functionality. In doing so, they created a further generalization--the idea of a precode. Recently, Drs. Blakley, Borosh, and A. Klappenecker have worked on interpreting the structures and results in these pioneering papers within the framework of category theory. The purpose of this dissertation is to further the above work. In particular, we seek to accomplish the following tasks within the ``general theory of codes.' 1. Rewrite the original two papers in terms of the alternate representations of precodes as bipartite digraphs and Boolean matrices. 2. Count various types of bipartite graphs up to isomorphism, and count various classes of codes and precodes up to isomorphism. 3. Identify many of the classical objects and morphisms from category theory within the categories of codes and precodes. 4. Describe the various ways of constructing a code from a precode by ``splitting' the precode. Identify important properties of these constructions and their interrelationship. Discuss the properties of the constructed codes with regard to the factorization of homomorphisms through them, and discuss their relationship to the code constructed from the precode by ``smashing.' 5. Define a parametrization of a precode and give constructions of various parametrizations of a given precode, including a ``minimal' parametrization. 6. Use the computer algebra system, Maple, to represent and display a precode and its companion, opposite, smash, split, bald-split, and various parametrizations. Implement the formulae developed for counting bipartite graphs and precodes up to isomorphism.