Sublinear Average-Case Shortest Paths in Weighted Unit-Disk Graphs.
Adam KarczmarzJakub PawlewiczPiotr SankowskiPublished in: SoCG (2021)
Keyphrases
- average case
- shortest path
- weighted graph
- finding the shortest path
- betweenness centrality
- edge weights
- worst case
- worst case analysis
- uniform distribution
- road network
- graph partitioning
- shortest path algorithm
- graph model
- strongly connected components
- travel time
- path length
- geodesic distance
- graph search
- average case complexity
- complex networks
- np hard
- spanning tree
- optimal path
- reinforcement learning
- theoretical analysis
- upper bound
- special case