Doctoral Dissertations

Keywords and Phrases

Dynamic Graph; Graph Theory; High Performance Computing

Abstract

A complex system of interacting entities in contemporary scenarios, be it biological, technological, or social, can be represented using graphs. Dynamic graphs, unlike their static counterparts, are ones in which the underlying topology changes over time. These networks act as a model for numerous systems, from transportation to social interactions, capturing the ever-evolving nature of real-world phenomena. However, the inherent temporality of these networks presents a unique set of challenges and the traditional static graph algorithms often fall short in efficiency and applicability. In our research, we delve into the complexities presented by large dynamic networks and suggest various methodologies to address them. Topological changes in dynamic networks often lead to temporal variations in the network properties. Repeatedly recomputing these properties can be resource-intensive and time-consuming. To address this, we first introduce a generic template that leverages past computed values and present network modifications to update graph properties efficiently. Utilizing this framework, we develop parallel algorithms tailored for the updating of single and multi-objective shortest paths, as well as vertex coloring. Furthermore, using our shortest path update algorithms to determine efficient routes for drone-based deliveries under varying wind conditions accentuates the practicality and importance of our methods in dynamic environments. Our research also explores resilient substructures in dynamic networks that retain their intrinsic properties and functionalities despite minor disruptions. We introduce \textit{robust spanners} in dynamic social networks that ensure effective information dissemination even with link or node failures, enhancing the network's robustness and functionality.

Advisor(s)

Das, Sajal K.

Committee Member(s)

Tripathy, Ardhendu S.
Bhowmick, Sanjukta
Nadendla, V. Sriram Siddhardh
Liang, Xin

Department(s)

Computer Science

Degree Name

Ph. D. in Computer Science

Publisher

Missouri University of Science and Technology

Publication Date

Spring 2025

Pagination

xv, 199 pages

Note about bibliography

Includes_bibliographical_references_(pages 183-198)

Rights

© 2025 Arindam Khanda , All Rights Reserved

Document Type

Dissertation - Open Access

File Type

text

Language

English

Thesis Number

T 12496

Download

Share

 
COinS