39 citations · 89 across the 25 of their papers we have counts for
4 papers · 1 filter
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…
Strengthening Hadwiger's conjecture for - and -chromatic graphs
Anders Martinsson, Raphael Steiner
Hadwiger's famous coloring conjecture states that every -chromatic graph contains a -minor. Holroyd [Bull. London Math. Soc. 29, (1997), pp. 139--144] conjectured the follo…
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…
Optimal schemes for combinatorial query problems with integer feedback
Anders Martinsson
A query game is a pair of a set of queries and a set of functions, or codewords We think of this as a two-player game. One player, Co…