Scalable Parallel Graph Algorithms – Prof. Sajal Das

ABSTRACT: Many real-world networks (e.g., wireless mobile networks, IoT and drone networks, disaster response networks, social and biological networks, transportation networks) are modeled as dynamic graphs characterized by their evolving nature, such as node/edge insertions and deletions, and edge weight modifications. Managing dynamic graph updates in parallel poses unique challenges. In this talk, we will design a framework for designing scalable parallel algorithms that aims to efficiently update graph properties in large scale dynamic networks instead of recomputing them from scratch. To demonstrate the efficacy of our framework, we will present scalable parallel algorithms for updating simple graph properties, such as single source shortest path, minimum spanning tree, vertex color, and multi-objective shortest path. We will apply our approach to energy-optimized path planning in unmanned aerial vehicle (UAV)-based delivery system in presence of environment dynamics (changing wind speed and direction). Extensive experimental results will demonstrate the performance of our proposed algorithms on shared memory parallel machines and GPU architectures.

BIORAPHY: Dr. Sajal K. Das is a Curators’ Distinguished Professor and Daniel St. Clair Endowed Chair in Computer Science at Missouri University of Science and Technology, where he was the Chair of Computer Science Department during 2013-2017. In the past, he served the US National Science Foundation (NSF) as a Program Director in the Computer and Network Systems Division.

Dr. Das’ interdisciplinary research spans cyber-physical systems, IoT, cybersecurity, data science, machine learning, wireless and sensor networks, mobile and pervasive computing, smart environments, parallel computing, edge/cloud computing, social and biological networks, graph theory and game theory. He has contributed significantly to these areas and published extensively (more than 350 journal articles and more than 450 peer-reviewed conference papers), coauthored four books, and 5 US patents. He directed over $20 million funded projects. His h-index is 99 with 39,000+ citations according to Google Scholar.

Dr. Das is the founding Editor-in-Chief of Elsevier’s Pervasive and Mobile Computing journal and serves as an Associate Editor of the IEEE Transactions on Mobile Computing, IEEE Transactions on Dependable and Secure Computing, IEEE/ACM transactions on Networking, ACM Transactions on Sensor Networks, Journal of Parallel and Distributed Computing. A (co)-founder of IEEE PerCom, WoWMoM, SMARTCOMP and ACM ICDCN conferences, he has served as General and Program Chair of reputed conferences. He is a recipient of 12 Best Paper Awards in prestigious conferences including ACM MobiCom and IEEE PerCom; and numerous awards for teaching, mentoring and research including the IEEE Computer Society’s Technical Achievement award for pioneering contributions to sensor networks and mobile computing, and the University of Missouri System President’s Award for Sustained Career Excellence. Dr. Das has mentored 12 postdoctoral fellows, 50 Ph.D. scholars, 31 MS thesis, and numerous undergraduate research students. He is a Distinguished alumnus of the Indian Institute of Science at Bangalore, and an IEEE Fellow.