A spectral approach to the shortest path problem

DOI10.1016/j.laa.2021.02.013zbMath1475.05058arXiv2004.01163OpenAlexW3132950972MaRDI QIDQ2020688

Stefan Steinerberger

Publication date: 24 April 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.01163

zbMATH Keywords

hot spotsspectral theoryshortest path problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Distance in graphs (05C12)

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Geodesic distance and curves through isotropic and anisotropic heat equations on images and surfaces
• Nodal sets for solutions of elliptic equations
• Path planning with divergence-based distance functions
• A variational approach to the consistency of spectral clustering
• The hot spots problem in planar domains with on hole
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• An O(m log log D) algorithm for shortest paths
• Rearrangements and convexity of level sets in PDE
• Nodal sets of eigenfunctions on Riemannian manifolds
• On the nodal line of the second eigenfunction of the Laplacian in \(\mathbb{R}^ 2\)
• Nodal sets of eigenfunctions on Riemann surfaces
• A counterexample to the ``hot spots conjecture
• On the ``hot spots conjecture of J. Rauch
• Nodal lines of eigenfunctions of the fixed membrane problem in general convex domains
• Fiber Brownian motion and the ``hot spots problem
• On nodal lines of Neumann eigenfunctions
• A new approach to all-pairs shortest paths on real-weighted graphs
• Shortest paths algorithms: Theory and experimental evaluation
• Asymptotics of the first nodal line of a convex domain
• A planar convex domain with many isolated ``hot spots on the boundary
• Properly-weighted graph Laplacian for semi-supervised learning
• Euclidean triangles have no hot spots
• Schur reduction of trees and extremal entries of the Fiedler vector
• Diffusion maps
• A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• Spectral Sparsification of Graphs
• Scaling coupling of reflecting Brownian motions and the hot spots problem
• Undirected single-source shortest paths with positive integer weights in linear time
• On a routing problem
• Solutions of the Shortest-Route Problem—A Review
• Hot spots in convex domains are in the tips (up to an inradius)
• Nodal sets of solutions of elliptic and parabolic equations
• Neumann Domains on Graphs and Manifolds
• Nodal Sets for Eigenfunctions of the Laplacian On Surfaces
• The “hot spots” conjecture for a certain class of planar convex domains
• Computing geodesic paths on manifolds
• Efficient Algorithms for Shortest Paths in Sparse Networks
• The size of the first eigenfunction of a convex planar domain
• Diffusion processes in a small time interval
• On Neumann eigenfunctions in lip domains
• The “hot spots” conjecture for domains with two axes of symmetry
• Closed Nodal Lines and Interior Hot Spots of the Second Eigenfunctions of the Laplacian on Surfaces
• On the Location of Maxima of Solutions of Schrödinger's Equation
• The game theoreticp-Laplacian and semi-supervised learning with few labels
• An inequality for potentials and the 'hot-spots' conjecture
• Distance Transform Gradient Density Estimation Using the Stationary Phase Approximation
• Locating the first nodal linein the Neumann problem
• A continuum limit for the PageRank algorithm
• Fibonacci heaps and their uses in improved network optimization algorithms
• Faster all-pairs shortest paths via circuit complexity
• Distance Functions and Geodesics on Submanifolds of $\R^d$ and Point Clouds
• Sparsified Cholesky and multigrid solvers for connection laplacians
• A Nearly-m log n Time Solver for SDD Linear Systems
• Hamilton Circuits of Convex Trivalent Polyhedra (Up to 18 Vertices)
• Isoperimetric Inequalities and Their Applications
• Diffusion processes in a small time interval
• A Theorem on Boolean Matrices
• Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces

This page was built for publication: A spectral approach to the shortest path problem