 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
|
|