Booth Id:
MATH026T
Category:
Year:
2015
Finalist Names:
Medarametla, Dhruv
Xu, Justin
Abstract:
Graph theory, a subfield of mathematics, is a versatile subject, able to be applied to numerous other fields such as computer science, sociology, and the physical sciences. Complex networks found in these fields, such as social networks and computer systems, can be modeled with nodes and links, and the resulting structure can be easily analyzed with graph theory. One important part of network analysis is fault diagnosis--determining how susceptible a network is to system errors or outside interference. This project considers a new type of network--the 2-Bijective Connection Network, or the 2-BCN--and its resilience with respect to both link and node deletion. In the former case, we created a recursive bound on a certain characteristic of the 2-BCN and used it to develop an explicit formula for the robustness of the 2-BCN network with respect to link deletions. In the latter case, we utilized a more generalized form of the Principle of Mathematical Induction in order to create another explicit bound--this one with respect to node deletion--for the resilience of the 2-BCN. Both of these results were asymptotically tight. In addition to these calculations, we analyzed the 2-BCN with another measure of robustness, as well as finding various miscellaneous properties of the network. Through our research, we found that the 2-BCN had many beneficial properties compared to other networks; for example, its versatility makes its implementation easier and also makes its repair quicker in event of node or link failures. With the development of a stable network, society benefits from the high speed computations offered by parallel computing; thus, the advantageous properties of 2-BCNs suggest that it is a viable and superior option for future parallel processing networks.