@inproceedings{7edf1fe9e57747a08e4e75511edd5666,
title = "Sublinear Time Shortest Path in Expander Graphs",
abstract = "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.",
keywords = "Breadth First Search, Expanders, Graph Algorithms, Shortest Path",
author = "Noga Alon and Allan Gr{\o}nlund and J{\o}rgensen, \{S{\o}ren Fuglede\} and Larsen, \{Kasper Green\}",
note = "Publisher Copyright: {\textcopyright} Noga Alon, Allan Gr{\o}nlund, S{\o}ren Fuglede J{\o}rgensen, and Kasper Green Larsen.; 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024 ; Conference date: 26-08-2024 Through 30-08-2024",
year = "2024",
month = aug,
doi = "10.4230/LIPIcs.MFCS.2024.8",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Dagstuhl Publishing",
pages = "8:1--8:13",
editor = "Rastislav Kralovic and Antonin Kucera",
booktitle = "49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024",
address = "Germany",
}