Lemmings.world
  • Communities
  • Create Post
  • Create Community
  • heart
    Support Lemmy
  • search
    Search
  • Login
  • Sign Up
tb4p@lemmy.ml to Computer Science@lemmy.mlEnglish · 2 years ago

Sublinear Time Shortest Path in Expander Graphs

arxiv.org

external-link
message-square
0
link
fedilink
1
external-link

Sublinear Time Shortest Path in Expander Graphs

arxiv.org

tb4p@lemmy.ml to Computer Science@lemmy.mlEnglish · 2 years ago
message-square
0
link
fedilink
Computing a shortest path between two nodes in an undirected unweighted graph is among the most basic algorithmic tasks. Breadth first search solves this problem in linear time, which is clearly also a lower bound in the worst case. However, several works have shown how to solve this problem in sublinear time in expectation when the input graph is drawn from one of several classes of random graphs. In this work, we extend these results by giving sublinear time shortest path (and short path) algorithms for expander graphs. We thus identify a natural deterministic property of a graph (that is satisfied by typical random regular graphs) which suffices for sublinear time shortest paths. The algorithms are very simple, involving only bidirectional breadth first search and short random walks. We also complement our new algorithms by near-matching lower bounds.
alert-triangle
You must log in or register to comment.

Computer Science@lemmy.ml

compsci@lemmy.ml

Subscribe from Remote Instance

Create a post
You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !compsci@lemmy.ml

A community dedicated for computer science topics; Everyone’s welcomed from student, lecturer, teacher to hobbyist!

Visibility: Public
globe

This community can be federated to other instances and be posted/commented in by their users.

  • 13 users / day
  • 13 users / week
  • 13 users / month
  • 13 users / 6 months
  • 2 local subscribers
  • 537 subscribers
  • 15 Posts
  • 0 Comments
  • Modlog
  • mods:
  • randomrhino@lemmy.ml
  • BE: 0.19.11
  • Modlog
  • Instances
  • Docs
  • Code
  • join-lemmy.org