Shai Gutner's home page
I completed my Ph.D. in Computer Science at the
TelAviv University
under the supervision of
Prof. Noga Alon
and
Prof. Yossi Azar.
Email: shai.gutner@cs.tau.ac.il
Major interests
 Online and Approximation Algorithms
 Pseudorandomness and Derandomization
 Parameterized Complexity
 Graph Choosability
Papers published

N. Alon and S. Gutner, Balanced hashing, color coding and approximate counting,
Proc. of 4th IWPEC (2009), 116.
[ps]
[pdf]

S. Gutner, Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded
minor,
Proc. of 4th IWPEC (2009), 246257.
[ps]
[pdf]

S. Gutner and M. Tarsi, Some results on (a:b)choosability,
Discrete Mathematics 309 (8) (2009), 22602270.
[ps]
[pdf]

S. Gutner, Elementary approximation algorithms for prize collecting Steiner tree problems,
Proc. of 2nd COCOA (2008), 246254.
[ps]
[pdf]
Also:
Information Processing Letters 107 (1) (2008), 3944.

N. Alon and S. Gutner, Linear time algorithms for finding a dominating set of fixed size in degenerated graphs,
Proc. of 13th COCOON (2007), 394405.
[ps]
[pdf]
Also: Algorithmica 54 (4) (2009), 544556.

N. Alon and S. Gutner, Balanced families of perfect hash functions and their applications,
Proc. of 34th ICALP (2007), 435446.
[ps]
[pdf]
Also: ACM
Transactions on Algorithms 6 (3) (2010).

Y. Azar, I. Gamzu and S. Gutner, Truthful unsplittable flow for large capacity networks,
Proc. of 19th SPAA (2007), 320329.
[ps]
[pdf]
Also: ACM
Transactions on Algorithms 6 (2) (2010).

N. Alon, Y. Azar and S. Gutner, Admission control to minimize rejections and online set cover with repetitions,
Proc. of 17th SPAA (2005), 238244.
[ps]
[pdf]
Also: ACM
Transactions on Algorithms 6 (1) (2009).

S. Gutner, The complexity of planar graph choosability,
Discrete Mathematics 159 (13) (1996), 119130.
[ps]
[pdf]
Theses

S. Gutner, Algorithms for optimization problems on networks and graphs,
Ph.D. thesis, TelAviv University, 2009.
[ps]
[pdf]
[Hebrew doc]
[Hebrew pdf]

S. Gutner, Choice numbers of graphs,
M.Sc. thesis, TelAviv University, 1992.
[ps]
[pdf]
Past courses
Useful links