Arindam Khanda

Arindam Khanda

Auto-generated profile, based on publicly available information

Arindam Khanda

Department of Computer Science, Missouri University of Science and Technology, Rolla, MO, USA

Research Focus & Metrics

Academic Career Length

6Years (2021-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
26 May 2021 in IEEE Transactions on Parallel and Distributed Systems
Verified
Journal Article
Closed access
AKArindam Khanda
Arindam Khanda
SSSriram Srinivasan
Sriram Srinivasan
SBSanjukta Bhowmick
Sanjukta Bhowmick
BNBoyana Norris
Boyana Norris
SSajal K. Das
Sajal K. Das
The Single Source Shortest Path (SSSP) problem is a classic graph theory problem that arises frequently in various practical scenarios; hence, many parallel algorithms have been developed to solve it. However, these algorithms operate on static graphs, whereas many real-world problems are best modeled as dynamic networks, where the structure of the network changes with time. This gap between the dynamic graph modeling and the assumed static graph model in the conventional SSSP algorithms motivates this work. We present a novel parallel algorithmic framework for updating the SSSP in large-scale dynamic networks and implement it on the shared-memory and GPU platforms. The basic idea is to identify the portion of the network affected by the changes and update the information in a rooted tree data structure that stores the edges of the network that are most relevant to the analysis. Extensive experimental evaluations on real-world and synthetic networks demonstrate that our proposed parallel updating algorithm is scalable and, in most cases, requires significantly less execution time than the state-of-the-art recomputing-from-scratch algorithms.

30 January 2025 in IEEE Transactions on Parallel and Distributed Systems
Verified
Journal Article
Closed access
SSS.M. Shovan
S.M. Shovan
AKArindam Khanda
Arindam Khanda
SSajal K. Das
Sajal K. Das
The multi objective shortest path (MOSP) problem, crucial in various practical domains, seeks paths that optimize multiple objectives. Due to its high computational complexity, numerous parallel heuristics have been developed for static networks. However, real-world networks are often dynamic where the network topology changes with time. Efficiently updating the shortest path in such networks is challenging, and existing algorithms for static graphs are inadequate for these dynamic conditions, necessitating novel approaches. Here, we first develop a parallel algorithm to efficiently update a single objective shortest path (SOSP) in fully dynamic networks, capable of accommodating both edge insertions and deletions. Building on this, we propose DynaMOSP, a parallel heuristic for Dynamic Multi Objective Shortest Path searches in large, fully dynamic networks. We provide a theoretical analysis of the conditions to achieve Pareto optimality. Furthermore, we devise a dedicated shared memory CPU implementation along with a version for heterogeneous computing environments. Empirical analysis on eight real-world graphs demonstrates that our method scales effectively. The shared memory CPU implementation achieves an average speedup of 12.74× and a maximum of 57.22×, while on an Nvidia GPU, it attains an average speedup of 69.19×, reaching up to 105.39× when compared to state-of-the-art techniques.

12 November 2023
Verified
Conference Paper
Open access
AKArindam Khanda
Arindam Khanda
SSS.M. Shovan
S.M. Shovan
SSajal K. Das
Sajal K. Das
In dynamic networks, where continuous topological changes are prevalent, it becomes paramount to find and update different graph properties without the computational burden of recalculating from the ground up. However finding or updating a multi-objective shortest path (MOSP) in such a network is challenging, as it involves simultaneously optimizing multiple (conflicting) objectives. In light of this, our paper focuses on shortest path search and proposes parallel algorithms tailored specifically for large incremental graphs. We first present an efficient algorithm that updates the single-objective shortest path (SOSP) whenever a new set of edges are introduced. Leveraging this SOSP update algorithm, we also devise a novel heuristic approach to adaptively update a MOSP in large networks. Empirical evaluations on both real and synthetic incremental networks with shared memory implementations attest to the scalability and efficacy of the proposed algorithms.

4 January 2025
Verified
Conference Paper
Open access
AKArindam Khanda
Arindam Khanda
ASAnurag Satpathy
Anurag Satpathy
AVAnusha Vangala
Anusha Vangala
SSajal K. Das
Sajal K. Das

4 January 2023
Verified
Conference Paper
Open access
AKArindam Khanda
Arindam Khanda
SSajal K. Das
Sajal K. Das
Graph queries on large networks leverage the stored graph properties to provide faster results. Since real-world graphs are mostly dynamic, i.e., the graph topology changes over time, the corresponding graph attributes also change over time. In certain situations, recompiling or updating earlier properties is necessary to maintain the accuracy of a response to a graph query. Here, we first propose a generic framework for developing parallel algorithms to update graph properties on large dynamic networks. We use our framework to develop algorithms for updating Single Source Shortest Path (SSSP) and Vertex Color. Then we propose applications of the developed algorithms in Unmanned Aerial Vehicle (UAV) based delivery systems under time-varying dynamics. Finally, we implement our SSSP and vertex color update algorithms for Nvidia GPU architecture and show empirically that the developed algorithms can update properties in large dynamic networks faster than the state-of-the-art techniques.