{"id":"arxiv/2608.25212","url":"https://arxiv.org/abs/2608.25212","tags":["cs.DS","cs.CC","cs.DM","math.CO"],"score":0,"title":"Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity","domain":"cs.DS","source":"arxiv","authors":["Édouard Bonnet","Julien Duron","Marcin Pilipczuk","Marek Sokołowski","Szymon Toruńczyk"],"reviews":0,"subject":"cs.DS","summary":"The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excluding a fixed (topological) minor, or bounded expansion graphs, as well as many structured classes of dense graphs, such as graphs of bounded clique-width, twin-width, merge-width, or flip-width. In this work, we present $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: $\\bullet$ All-Pairs Shortest Paths, $\\bullet$ the multiplication…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-25","reactions":{}}