105 citations · 381 across the 31 of their papers we have counts for
5 papers · 1 filter
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
Noga Alon, Shai Gutner
There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a time al…
Balanced Families of Perfect Hash Functions and Their Applications
Noga Alon, Shai Gutner
The construction of perfect hash functions is a well-studied topic. In this paper, this concept is generalized with the following definition. We say that a family of functions from…
Spanning directed trees with many leaves
N Alon, F. V. Fomin, G. 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…
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…
Parameterized Algorithms for Directed Maximum Leaf Problems
Noga Alon, Fedor Fomin, Gregory Gutin +2
We prove that finding a rooted subtree with at least leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with m…