Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time.
Monika HenzingerSebastian KrinningerDanupon NanongkaiPublished in: FOCS (2014)
Keyphrases
- shortest path problem
- single source
- shortest path
- undirected graph
- directed graph
- directed acyclic graph
- shortest path algorithm
- road network
- approximation algorithms
- routing algorithm
- travel time
- spanning tree
- path length
- weighted graph
- graph structure
- finding the shortest path
- databases
- combinatorial optimization problems
- minimum cost
- connected components
- special case