• DocumentCode
    707407
  • Title

    Kth shortest path for dynamic edges

  • Author

    Rawal, Yashasvi ; Basra, Vishal ; Ahuja, Anmol ; Garg, Bindu

  • Author_Institution
    BVCOE, GGSIPU, New Delhi, India
  • fYear
    2015
  • fDate
    11-13 March 2015
  • Firstpage
    1000
  • Lastpage
    1003
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computing for Sustainable Global Development (INDIACom), 2015 2nd International Conference on
  • Conference_Location
    New Delhi
  • Print_ISBN
    978-9-3805-4415-1
  • Type

    conf

  • Filename
    7100397