Routing Algorithms As An Application Of Graph Theory

Download

Gokberk_Yildirim_Master_Thesis__2071728.pdf

Date

2023-1-27

Author

Yıldırım, Gökberk

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

727
views

1557
downloads

This paper examines routing algorithms that are generally used in various network types, such as Internet Protocol in graph-based models, to find the shortest routing path or minimum cost. The fundamental approach for calculating the shortest path between one point to another is searching a given graph, starting at the source node, and traversing adjacent nodes until the destination node is reached. The aim is to identify the shortest routing path to the destination node. This paper searches well-known routing algorithms, namely Bellman-Ford and Dijkstra's single source shortest path algorithms, and their application areas like network communication protocols, a cryptocurrency exchange in arbitrage, and vertex-weighted directed graphs in robotics. The paper aims to decrease the number of blocked path requests and improve overall usage, especially in cryptographic tools. The routing algorithms are analyzed and defined with uncertainty arising from various factors, such as weather conditions and road capacity at specific times. The main challenges in the Shortest Path Algorithms (SPP) are identifying which edges to add and comparing the distances between different paths based on their edge lengths.

Subject Keywords

Bellman-Ford, Dijkstra, shortest path, routing algorithms, communication networks, directed graphs, minimum cycle path

URI

https://hdl.handle.net/11511/102142

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

Relay Selection for Efficient HARQ-IR Protocols in Relay-Assisted Multisource Multicast Networks Quoc-Tuan Vien, Quoc-Tuan Vien; Nguyen, Huan X.; Shah, Purav; Ever, Enver; Duc To, Duc To (2014-05-21) This paper investigates relay selection for reliable data transmission in relay-assisted multisource multicast networks (RMMNs) where multiple source nodes distribute information to a set of destination nodes with the assistance of multiple relay nodes. Hybrid automatic repeat request with incremental redundancy (HARQ-IR) is used and supported by either a physical-layer network coding (PNC) or an analog network coding (ANC) technique employed at the relays. By deriving efficiency metrics of the HARQ-IR prot...
Path planning for mobile-anchor based wireless sensor network localization: Static and dynamic schemes Erdemir, Ecenaz; Tuncer, Temel Engin (Elsevier BV, 2018-08-01) In wireless sensor networks, node locations are required for many applications. Usually, anchors with known positions are employed for localization. Sensor positions can be estimated more efficiently by using mobile anchors (MAs). Finding the best MA trajectory is an important problem in this context. Various path planning algorithms are proposed to localize as many sensors as possible by following the shortest path with minimum number of anchors. In this paper, path planning algorithms for MA assisted loca...
TRACEMIN Fiedler A Parallel Algorithm for Computing the Fiedler Vector Manguoğlu, Murat; Saied, Faisal; Sameh, Ahmed (null; 2010-06-25) The eigenvector corresponding to the second smallest eigenvalue of the Laplacian of a graph, known as the Fiedler vector, has a number of applications in areas that include matrix reordering, graph partitioning, protein analysis, data mining, machine learning, and web search. The computation of the Fiedler vector has been regarded as an expensive process as it involves solving a large eigenvalue problem. We present a novel and efficient parallel algorithm for computing the Fiedler vector of large graphs bas...
Cooperative Multiple-Access in Fading Relay Channels Yılmaz, Ayşen (2006-06-15) Virtual antenna arrays can be constructed via relaying even in the case that there is insufficient physical space or other resources for multiple antennae on wireless nodes. When there is a multiple access scenario, relaying offers a variety of ways to establish communication between source and destination nodes. We will compare a scheme based on space division multiple access to previously studied time division based ones. We observe that space division improves especially the ergodic capacity.
Evaluation of Terahertz Channel in Data Centers MOLLAHASANİ, Shahram; Onur, Ertan (2016-04-29) Designing data center network topologies with the objective of minimizing cost, increasing bisection bandwidth and decreasing latency is a difficult problem. The solutions in the literature mainly concentrate on wired networks and minimizing wiring costs thereof. Only a few proposals address the benefit of employing wireless communications in data centers due to spectrum and bandwidth limitations of current wireless communication technologies. By using terahertz communication in a data center as a complemen...

Citation Formats

G. Yıldırım, “Routing Algorithms As An Application Of Graph Theory,” M.S. - Master of Science, Middle East Technical University, 2023.