Faster algorithms for shortest path and network flow based on graph decomposition.
Manas Jyoti KashyopTsunehiko NagayamaKunihiko SadakanePublished in: J. Graph Algorithms Appl. (2019)
Keyphrases
- shortest path
- strongly connected components
- network flow
- shortest path algorithm
- edge weights
- minimum spanning tree
- shortest path problem
- graph search
- weighted graph
- graph theory
- path length
- road network
- finding the shortest path
- minimum cost flow
- min cost
- betweenness centrality
- flow graph
- network flow formulation
- random walk
- optimization problems
- worst case
- combinatorial optimization problems
- travel time
- tree decomposition
- minimum cost
- np complete
- computational complexity
- optimal solution
- social networks