Meeting times on graphs in near-cubic time

Alex McAvoy · 2026

Read Meeting times on graphs in near-cubic time by Alex McAvoy (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18872.txt.

Description

McAvoy gives a simple algorithm for the expected meeting time of two random walkers on an undirected graph, where one walker moves per step until collision. Naively solving the system of linear equations for all meeting times takes sixth power operations. The method exploits the near Sylvester structure of the system, with only a diagonal absorption constraint as obstruction, cutting cost to fourth power operations and quadratic space. A theoretical refinement using Cauchy structure reaches near cubic time, and extends to the Poisson equation for the absorbing lazy pair walk.

Catalog record

CREATORAlex McAvoy
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24088
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.18872

Browse the full library · About the Tower of Babel