5 citations · 6 across the 4 of their papers we have counts for
14 papers
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň, Bernhard Haeupler, Anders Martinsson +2
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorith…
Cycle lengths modulo in expanders
Anders Martinsson, Raphael Steiner
Given a constant , an -vertex graph is called an -expander if every set of at most vertices in has an external neighborhood of size at least . Addres…
Arithmetic Progressions in Sumsets of Sparse Sets
Noga Alon, Ryan Alweiss, Yang P. Liu +2
A set of positive integers is \emph{log-sparse} if there is an absolute constant so that for any positive integer the sequence contains at most…
Note on Long Paths in Eulerian Digraphs
Charlotte Knierim, Maxime Larcher, Anders Martinsson
Long Paths and Cycles in eulerian digraphs have gotten a lot of attention recently. In this short note, we show how to use methods from Knierim, Larcher, Martinsson, Noever (2021)…
The Chromatic Number of Dense Random Block Graphs
Anders Martinsson, Konstantinos Panagiotou, Pascal Su +1
The chromatic number of a graph , that is, the smallest number of colors required to color the vertices of so that no two adjacent vertices are assigned the same colo…
Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs
Charlotte Knierim, Maxime Larcher, Anders Martinsson +1
Hajós conjectured in 1968 that every Eulerian \(n\)-vertex graph can be decomposed into at most edge-disjoint cycles. This has been confirmed for some spec…