Sublinear time shortest path in expander graphs

DOI10.4230/LIPICS.MFCS.2024.8MaRDI QIDQ7241004zbMATH OpenFDO

Authors Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2024.8

zbMATH Keywords

breadth first searchexpandersgraph algorithmsshortest path

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A bidirectional shortest-path algorithm with good average-case behavior
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A proof of Alon’s second eigenvalue conjecture and related problems
• An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs
• An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs
• An Improved Bidirectional Heuristic Search Algorithm
• Bidirectional Heuristic Search Again
• Cutoff on all Ramanujan graphs
• Derandomized graph products
• Deterministic performance guarantees for bidirectional BFS on real-world networks
• Diameters and Eigenvalues
• Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
• Eigenvalues and expanders
• Expander graphs and their applications
• Explicit expanders of every degree and size
• High-girth near-Ramanujan graphs with localized eigenvectors
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
• Some problems in the enumeration of labelled graphs
• The asymptotic number of non-negative integer matrices with given row and column sums

This page was built for publication: Sublinear time shortest path in expander graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241004)