Title :
Kth shortest path for dynamic edges
Author :
Rawal, Yashasvi ; Basra, Vishal ; Ahuja, Anmol ; Garg, Bindu
Author_Institution :
BVCOE, GGSIPU, New Delhi, India
Abstract :
In our approach to find a suitable means for accessing and traversing a graph with edges that have the some alternating weight assigned to them. We studied combinational properties of graphs, thus allowing us to come to a newer and easier method to fully traverse a dynamic graph that stimulates the real-time environment with the weight upon its edges changing continuously. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative edges with weights that are revalued continuously. The sequence of operations remains to be in O(n2) amortized time per update and unit worst-case time per distance query, where n is the number of vertices. The focus of our study is to primarily ensure that in an environment where several nodes co-exist with weights and paths on the edges sprouting irregularly, there is still a palpable method to calculate the shortest path. Our algorithm is deterministic, uses simple data structures thus is efficient to be employed for its goal.
Keywords :
computational complexity; deterministic algorithms; directed graphs; amortized time; combinational properties; data structures; deterministic algorithm; distance query; dynamic edges; dynamic graph; general directed graphs; kth shortest path; nonnegative edges; real-time environment; unit worst-case time; vertices; Algorithm design and analysis; Arrays; Digital signal processing; Electronic mail; Heuristic algorithms; Real-time systems; Dynamic; Edge Update; alternating edges; interim traversal update; shortest path;
Conference_Titel :
Computing for Sustainable Global Development (INDIACom), 2015 2nd International Conference on
Conference_Location :
New Delhi
Print_ISBN :
978-9-3805-4415-1