Analysis of Topological Sort Algorithm for the Connectivity and Complexity of an Interconnection Network
International Journal of Scientific Research in Science, Engineering and Technology · 20.06.2026 · 13 (3) · 508-514
DOI: 10.32628/ijsrset2613365 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Scientific Research in Science, Engineering and Technology, online erschienen am 20.06.2026. Verfasst von Bhimnarayan Tiwari und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
This paper analyzes in detail the basic principles of topological sort algorithms, their mechanisms and their applications in interconnection networks. While both Kan's algorithm and DFS-based methods have a time complexity of (𝑉+𝐸), it is worth noting that their performance depends on the graph structure, memory management and node selection technique. In particular, these legacy methods do not consider node priority or network-aware processing, which becomes a bottleneck in large and complex interconnection networks. Considering these limitations, this chapter proposes a new algorithm called Priority-Based Layered Topological Sort (PLTS). This method combines the principles of layer-based decomposition, priority-driven selection, and hybrid processing to perform graph traversal in a more integrated and intelligent manner. Specifically, using a priority queue to select nodes based on their out-degree and connectivity scores optimizes traversal order and improves data flow. Although, the PLTS algorithm is not completely flawless. The priority calculations and queue operations can incur an additional overhead of (𝑉 log 𝑉), which can impact performance in some cases. Determining the connectivity score is application-specific, and results can vary if it is not properly defined and normalized.
Zitieren
APA
Tiwari, B., Pandey, S. P., & Katare, R. K. (2026). Analysis of Topological Sort Algorithm for the Connectivity and Complexity of an Interconnection Network. International Journal of Scientific Research in Science, Engineering and Technology, 13(3), 508-514. https://doi.org/10.32628/ijsrset2613365
Vancouver
Tiwari B, Pandey SP, Katare RK. Analysis of Topological Sort Algorithm for the Connectivity and Complexity of an Interconnection Network. International Journal of Scientific Research in Science, Engineering and Technology. 2026;13(3):508-514. doi:10.32628/ijsrset2613365
BibTeX
@article{Tiwari2026,
author = {Tiwari, Bhimnarayan and Pandey, Surya Prakash and Katare, Rakesh Kumar},
title = {Analysis of Topological Sort Algorithm for the Connectivity and Complexity of an Interconnection Network},
journal = {International Journal of Scientific Research in Science, Engineering and Technology},
year = {2026},
volume = {13},
number = {3},
pages = {508--514},
doi = {10.32628/ijsrset2613365}
}
EUVIMED