APPLICATIONS OF DYNAMIC GRAPH ALGORITHMS IN REAL-TIME TRAFFIC AND NETWORK OPTIMIZATION

Abstract

This paper presents an exhaustive survey of dynamic graph algorithms and their applications in real-time traffic and network optimization. We begin by establishing the theoretical foundations of dynamic graphs, providing a taxonomy of problem types and discussing the core data structures and complexity metrics that underpin the field. We then conduct a deep dive into seminal algorithms for fundamental dynamic graph problems, including connectivity (Link-Cut Trees), minimum spanning forests (Holm et al.), shortest paths (D* Lite), and maximum flow (time-expanded networks), presenting their operational logic and mathematical formalisms. The paper subsequently bridges theory and practice by detailing the application of these algorithms within Intelligent Transportation Systems (ITS), analyzing the complete data pipeline architecture from sensor ingestion to real-time traffic routing and signal control. Broader applications in communication, social, and security networks are also explored. Finally, we address the critical challenges of scalability, noisy data, and the integration of machine learning, concluding with a discussion on the future landscape, which is increasingly shaped by the convergence of dynamic graph neural networks and deep reinforcement learning. This survey serves as a definitive reference for researchers and practitioners, synthesizing the state-of-the-art and charting the course for future innovation.