105 citations · 379 across the 28 of their papers we have counts for
9 papers · 1 filter
Discrete Kakeya-type problems and small bases
Noga Alon, Boris Bukh, Benny Sudakov
A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and…
Large nearly regular induced subgraphs
Noga Alon, Michael Krivelevich, Benny Sudakov
For a real c \geq 1 and an integer n, let f(n,c) denote the maximum integer f so that every graph on n vertices contains an induced subgraph on at least f vertices in which the max…
Better Algorithms and Bounds for Directed Maximum Leaf Problems
Noga Alon, Fedor V. Fomin, Gregory Gutin +2
The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In th…
Additive approximation for edge-deletion problems
Noga Alon, Asaf Shapira, Benny Sudakov
A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following edge-deletion problem; given a monotone property P and a g…
Embedding nearly-spanning bounded degree trees
Noga Alon, Michael Krivelevich, Benny Sudakov
We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-ε)n vertices, in terms of the expansion properti…
On graphs with subgraphs of large independence numbers
Noga Alon, Benny Sudakov
Let G be a graph on n vertices in which every induced subgraph on s=\log^3 n vertices has an independent set of size at least t=\log n. What is the largest q=q(n) so that every suc…