7 citations · 12 across the 7 of their papers we have counts for
7 papers
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…
Truthful Unsplittable Flow for Large Capacity Networks
Yossi Azar, Iftah Gamzu, Shai Gutner
In this paper, we focus our attention on the large capacities unsplittable flow problem in a game theoretic setting. In this setting, there are selfish agents, which control some o…
Admission Control to Minimize Rejections and Online Set Cover with Repetitions
Noga Alon, Yossi Azar, Shai Gutner
We study the admission control problem in general networks. Communication requests arrive over time, and the online algorithm accepts or rejects each request while maintaining the…
The complexity of planar graph choosability
Shai Gutner
A graph is {\em -choosable} if for every assignment of a set of colors to every vertex of , there is a proper coloring of that assigns to each vertex $…
Choice numbers of graphs
Shai Gutner
A solution to a problem of Erdős, Rubin and Taylor is obtained by showing that if a graph is -choosable, and , then is not necessarily -choosable.…