Shai Gutner's home page
I completed my Ph.D. in Computer Science at the
Tel-Aviv University
under the supervision of
Prof. Noga Alon
and
Prof. Yossi Azar.
E-mail: 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,
ECCC Report TR09-012.
[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), to appear.
[ps]
[pdf]
-
S. Gutner and M. Tarsi, Some results on (a:b)-choosability,
Discrete Mathematics 309 (8) (2009), 2260-2270.
[ps]
[pdf]
-
S. Gutner, Elementary approximation algorithms for prize collecting Steiner tree problems,
Proc. of 2nd COCOA (2008), 246-254.
[ps]
[pdf]
Also:
Information Processing Letters 107 (1) (2008), 39-44.
-
N. Alon and S. Gutner, Linear time algorithms for finding a dominating set of fixed size in degenerated graphs,
Proc. of 13th COCOON (2007), 394-405.
[ps]
[pdf]
Also: Algorithmica 54 (4) (2009), 544-556.
-
N. Alon and S. Gutner, Balanced families of perfect hash functions and their applications,
Proc. of 34th ICALP (2007), 435-446.
[ps]
[pdf]
Also: ACM Transactions on Algorithms, to appear.
-
Y. Azar, I. Gamzu and S. Gutner, Truthful unsplittable flow for large capacity networks,
Proc. of 19th SPAA (2007), 320-329.
[ps]
[pdf]
Also: ACM Transactions on Algorithms, to appear.
-
N. Alon, Y. Azar and S. Gutner, Admission control to minimize rejections and online set cover with repetitions,
Proc. of 17th SPAA (2005), 238-244.
[ps]
[pdf]
Also: ACM Transactions on Algorithms, to appear.
-
S. Gutner, The complexity of planar graph choosability,
Discrete Mathematics 159 (1-3) (1996), 119-130.
[ps]
[pdf]
Theses
-
S. Gutner, Algorithms for optimization problems on networks and graphs,
Ph.D. thesis, Tel-Aviv University, 2009.
[ps]
[pdf]
[Hebrew doc]
[Hebrew pdf]
-
S. Gutner, Choice numbers of graphs,
M.Sc. thesis, Tel-Aviv University, 1992.
[ps]
[pdf]
Past courses
Useful links