After recognizing the beauty and the utility of Graph Theory in solving a variety of problems, the author decided that it would be a good idea to make the subject available for students earlier in their educational experience. In this thesis, the author developed four units in Graph Theory, namely Vertex Coloring, Minimum Spanning Tree, Domination, and Hamiltonian Paths and Cycles, which are appropriate for high school level.

In this report, we initiate study on understanding a theoretical model for distributed computing called Congested Clique. This report presents constant-time and near-constant-time distributed algorithms for a variety of problems in the Congested Clique model. We start by showing how to compute a 3-ruling set in expected O(log log log n) rounds and using this, we obtain a constant-approximation to metric facility location, also in expected O(log log log n) rounds. In addition, assuming an input metric space of constant doubling dimension, we obtain constant-round algorithms to compute maximal independent set on distance-threshold graphs and constant-factor approximation to the metric facility location problem. These results significantly improve on the running time of the fastest known algorithms for these problems in the Congested Clique setting. Then, we study two fundamental graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the Congested Clique model, and present several new bounds on the time and message complexities of randomized algorithms for these problems. No non-trivial (i.e., super-constant) time lower bounds are known for either of the aforementioned problems; in particular, an important open question is whether or not constant-round algorithms exist for these problems. We make progress toward answering this question by presenting randomized Monte Carlo algorithms for both problems that run in O(log log log n) rounds (where n is the size of the clique). In addition, assuming an input metric space of constant doubling dimension, we obtain constant-round algorithm the MST problem. Our results improve by an exponential factor on the long-standing (deterministic) time bound of O(log log n) rounds for these problems due to Lotker et al. (SICOMP 2005). Our algorithms make use of several algorithmic tools including graph sketching, random sampling, and fast sorting. Thus far there has been little work on understanding the message complexity of problems in the Congested Clique. In this report, we initiate a study on the message complexity of Congested Clique algorithms. We study two graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the Congested Clique model, focusing on the design of fast algorithms with low message complexity. Our motivation comes from recently established connections between the Congested Clique model and models of large-scale distributed computing such as MapReduce (Hegeman et al., SIROCCO 2014) and the “big data” model (Klauck et al., SODA 2015). For these connections to be fruitful, Congested Clique algorithms not only need to be fast, they also need to have low message complexity. While the aforementioned algorithms are fast, they have an Ω(n2) message complexity, which makes them impractical in the context of the MapReduce and “big data” models. This motivates our goal of achieving low message complexity, without sacrificing the speed of the algorithm. We start with the simpler GC problem and show that it can be solved in O(log log log n) rounds using only O(n poly log n) messages. Then we derive subroutines to aid our earlier MST algorithm to run in O(log log log n) rounds using O(m poly log n) messages on an m-edge input graph. Then, we present an algorithm running in O(log* n) rounds, with message complexity O (sqrt(m · n)) and then build on this algorithm to derive a family of algorithms, containing for any ε, 0 < ε ≤ 1, an algorithm running in O(log*n/ε) rounds, using O(n^(1+ε/ε)) messages. Setting ε = log log n/ log n leads to the first sub-logarithmic round Congested Clique MST algorithm that uses only O (n) messages. Our results are a step toward understanding the power of randomization in the Congested Clique with respect to both time and message complexity.

網路技術發展的日新月異帶領了眾多新網路服務的崛起，例如即時影音串流這類的多媒體服務。但即時影音串流服務所產生的龐大資料流和傳輸延遲時間的嚴格限制也隨之而來的為網路環境帶來許多挑戰，在這些條件下，傳統Server-client拓樸架構將client要求的影音資料以單一鏈結傳輸時，常會因為頻寬不足而面臨嚴重的封包遺失，或是資料流擁擠造成的額外傳輸延遲使得封包無法達到即時性的需求。P2P網路擁有server-client架構所難以達到的規模伸縮性，且對於節點、鏈結失效所引起的傳輸錯誤也較能容忍，更重要的是，它有效的分散了原本負載在少數link上的龐大資料流。因此P2P架構近年來風行於即時影音串流服務。 目前P2P網路的拓樸多是隨意形成，當網路成員規模龐大時，由傳送端出發到遠方的接收端，途中可能經過無數的鏈結，每一個鏈結都會由於頻寬的不足使得資料流遭受某種程度的品質損害，另一方面，對即時影音服務而言，若資料流的累積延遲時間超出可容忍範圍時，無法為使用者接受。 本研究嘗試找出一個較好的拓樸用以傳輸多媒體資料流，使得位於最遠端節點的累積延遲亦能為使用者接受，且資料品質的損害程度最小。我們將之建置成一NP-Complete複雜度的問題模型，名為MLDST。而解法則是修改Dijkstra single-source shortest-path演算法，並加上每個節點承擔下游節點數量及延遲時間限制而來。我們以PlanetLab環境在實際的網路上進行實驗，證實我們的演算法比傳統的Minimum-Spanning Tree及shortest path spanning tree有更好的影像品質。 / Numerous new network services arise with the advanced development of network technologies, such as real-time multimedia streaming services. But challenges to network environment come along with the enormous traffic of data flows and rigorous restriction to transmission delay of real-time multimedia streaming services. Under this circumstance, conventional server-client topology suffers from serious packet loss and packet delay due to the overload of servers and their accessing links. Also, extra transmission delay may make packets fail to meet the requirement of real-timed services. Peer-to-peer network is more scalable than server-client model, and is much more tolerable to the transmission errors caused by node or link failures. More importantly, it effectively distributes load from the server to peers. As a consequence, peer-to-peer service architecture becomes very popular for real-time multimedia streaming services recently. Peer-to-peer networks are mostly formed in random fashion. As the size of network grows, packets may have to travel through numerous links to reach far-end receivers. The quality of data may be damaged by insufficient bandwidth of links. For real-time multimedia services, it is not acceptable to users if the cumulated packet delay exceeds a tolerable limit. Our research is trying to find a better topology to transmit multimedia data flows which makes the cumulated delay of the most-far-end user be tolerable and the damage of data quality is minimized. The problem is modeled as a MLDST problem, which is a NP-Complete problem. To solve the problem, we modified Dijkstra’s single-source shortest-path algorithm by bounding the node degree and adding delay constraint. The experiments were carried out on real network environment through PlanetLab. Experiments show that our algorithm outperforms traditional MST and shortest path spanning tree.

In this thesis, we make some contributions at the interface between algebra and graph theory. In Chapter 1, we give an overview of the topics and also the definitions and preliminaries. In Chapter 2, we estimate the number of possible types degree patterns of k-lacunary polynomials of degree t < p which split completely modulo p. The result is based on a rather unusual combination of two techniques: a bound on the number of zeros of lacunary polynomials and a bound on the so-called domination number of a graph. In Chapter 3, we deal with the determinant of bipartite graphs. The nullity of a graph G is the multiplicity of 0 in the spectrum of G. Nullity of a (molecular) graph (e.g., a bipartite graph corresponding to an alternant hydrocarbon) has important applications in quantum chemistry and Huckel molecular orbital (HMO) theory. A famous problem, posed by Collatz and Sinogowitz in 1957, asks to characterize all graphs with positive nullity. Clearly, examining the determinant of a graph is a way to attack this problem. In this Chapter, we show that the determinant of a bipartite graph with at least two perfect matchings and with all cycle lengths divisible by four, is zero. In Chapter 4, we first introduce an application of spectral graph theory in proving trigonometric identities. This is a very simple double counting argument that gives very short proofs for some of these identities (and perhaps the only existed proof in some cases!). In the rest of Chapter 4, using some properties of the well-known Chebyshev polynomials, we prove some theorems that allow us to evaluate the number of spanning trees in join of graphs, Cartesian product of graphs, and nearly regular graphs. In the last section of Chapter 4, we obtain the number of spanning trees in an (r,s)-semiregular graph and its line graph. Note that the same results, as in the last section, were proved by I. Sato using zeta functions. But our proofs are much shorter based on some well-known facts from spectral graph theory. Besides, we do not use zeta functions in our arguments. In Chapter 5, we present the conclusion and also some possible projects.

This dissertation considers a subclass of sum-of-ratios fractional combinatorial optimization problems (FCOPs) whose linear versions admit polynomial-time exact algorithms. This topic lies in the intersection of two scarcely researched areas of fractional programming (FP): sum-of-ratios FP and combinatorial FP. Although not extensively researched, the sum-of-ratios problems have a number of important practical applications in manufacturing, administration, transportation, data mining, etc. Since even in such a restricted research domain the problems are numerous, the main focus of this dissertation is a mathematical programming study of the three, probably, most classical FCOPs: Minimum Multiple Ratio Spanning Tree (MMRST), Minimum Multiple Ratio Path (MMRP) and Minimum Multiple Ratio Cycle (MMRC). The first two problems are studied in detail, while for the other one only the theoretical complexity issues are addressed. The dissertation emphasizes developing solution methodologies for the considered family of fractional programs. The main contributions include: (i) worst-case complexity results for the MMRP and MMRC problems; (ii) mixed 0-1 formulations for the MMRST and MMRC problems; (iii) a global optimization approach for the MMRST problem that extends an existing method for the special case of the sum of two ratios; (iv) new polynomially computable bounds on the optimal objective value of the considered class of FCOPs, as well as the feasible region reduction techniques based on these bounds; (v) an efficient heuristic approach; and, (vi) a generic global optimization approach for the considered class of FCOPs. Finally, extensive computational experiments are carried out to benchmark performance of the suggested solution techniques. The results confirm that the suggested global optimization algorithms generally outperform the conventional mixed 0{1 programming technique on larger problem instances. The developed heuristic approach shows the best run time, and delivers near-optimal solutions in most cases.

With the increasing demand on multimedia applications over the Internet, and the growing number of mobile smart devices people are using, it is helpful to develop a mobile network architecture that can support multimedia transmission without using infrastructures. We propose that service overlay networks over MANETs can serve as a supplement to the existing 3G/4G networks and Wi-Fi access point networks. In this thesis we present experiment results that show the feasibility of mobile service overlay networks to meet the requirements of multimedia streaming. And also, we improved one of the existing overlay protocols. The improved protocol takes physical location into consideration when establishing connections in the overlay network. It also limits the number of neighbors each node can have, which prevents a particular node from becoming the bottleneck of the network, when connected to too many neighbors. Evaluation results show the new protocol reduces network packet loss rate.

With the increasing demand on multimedia applications over the Internet, and the growing number of mobile smart devices people are using, it is helpful to develop a mobile network architecture that can support multimedia transmission without using infrastructures. We propose that service overlay networks over MANETs can serve as a supplement to the existing 3G/4G networks and Wi-Fi access point networks. In this thesis we present experiment results that show the feasibility of mobile service overlay networks to meet the requirements of multimedia streaming. And also, we improved one of the existing overlay protocols. The improved protocol takes physical location into consideration when establishing connections in the overlay network. It also limits the number of neighbors each node can have, which prevents a particular node from becoming the bottleneck of the network, when connected to too many neighbors. Evaluation results show the new protocol reduces network packet loss rate.

In this thesis, we make some contributions at the interface between algebra and graph theory. In Chapter 1, we give an overview of the topics and also the definitions and preliminaries. In Chapter 2, we estimate the number of possible types degree patterns of k-lacunary polynomials of degree t < p which split completely modulo p. The result is based on a rather unusual combination of two techniques: a bound on the number of zeros of lacunary polynomials and a bound on the so-called domination number of a graph. In Chapter 3, we deal with the determinant of bipartite graphs. The nullity of a graph G is the multiplicity of 0 in the spectrum of G. Nullity of a (molecular) graph (e.g., a bipartite graph corresponding to an alternant hydrocarbon) has important applications in quantum chemistry and Huckel molecular orbital (HMO) theory. A famous problem, posed by Collatz and Sinogowitz in 1957, asks to characterize all graphs with positive nullity. Clearly, examining the determinant of a graph is a way to attack this problem. In this Chapter, we show that the determinant of a bipartite graph with at least two perfect matchings and with all cycle lengths divisible by four, is zero. In Chapter 4, we first introduce an application of spectral graph theory in proving trigonometric identities. This is a very simple double counting argument that gives very short proofs for some of these identities (and perhaps the only existed proof in some cases!). In the rest of Chapter 4, using some properties of the well-known Chebyshev polynomials, we prove some theorems that allow us to evaluate the number of spanning trees in join of graphs, Cartesian product of graphs, and nearly regular graphs. In the last section of Chapter 4, we obtain the number of spanning trees in an (r,s)-semiregular graph and its line graph. Note that the same results, as in the last section, were proved by I. Sato using zeta functions. But our proofs are much shorter based on some well-known facts from spectral graph theory. Besides, we do not use zeta functions in our arguments. In Chapter 5, we present the conclusion and also some possible projects.

Image segmentation has an important role in image processing because it is a tool to obtain higher level object descriptions for further processing. In some applications such as large image databases or video image sequence segmentations, the speed of the segmentation algorithm may become a drawback of the application. This thesis work is a study to improve the run-time performance of a well-known segmentation algorithm, namely the Recursive Shortest Spanning Tree (RSST). Both the original and the fast RSST found in the literature are analyzed and a comparison is made between these techniques. Simple modifications and an alternative link cost structure are proposed and evaluated. Finally, a distributed implementation based on a simple image partitioning strategy is attempted. The thesis presents the results of an extensive computational study with respect to both run-time performance and image segmentation quality.

Hlavním cílem této práce je vyložit a zejména propojit existující metodologii filtrování korelačních matic, grafových algoritmů aplikovaných na minimální kostry grafu, hierarchického shlukování a analýzy hlavních komponent, pro vytvoření kvantitativních investičních strategií. Namísto tradičního použití časových řad akciových výnosů je užito reziduí z faktorových modelů. Tato rezidua jsou klíčovým vstupem pro všechny používané algoritmy k výpočtu pravděpodobnosti středovosti dané akcie. Pravděpodobnost středovosti je nekonvenční ukazatel pravděpodobnosti, kde hodnota blízko 1 značí vysokou pravděpodobnost středovosti dané akcie v dané ekonomické síti. Na základě této míry pravděpodobnosti je vybudováno několik investičních strategií, které jsou dále testován hlavních amerických akciových indexů. Nemůže být generalizováno, že periferní strategie dosahují konzistentně lepších výsledků než středové strategie. Zatímco při použití klasického Markowitzova optimalizačního procesu jsou zisky stabilní a potenciál průměrný, oba typy vybudovaných strategií (středové i periferní) sdílí vysoký potenciál zisku, který je ovšem vykoupen vysokou volatilitou.