School of Technology and Computer Science Seminars

NP-Hardness of Art Gallery Problem & Terrain Guarding Problem

by Bodhayan Roy (School of Technology and Computer Science)

Monday, May 30, 2011 from to (Asia/Kolkata)
at Colaba Campus ( A-212 (STCS Seminarf Room) )
School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road Mumbai 400005
Description
This will be a talk on the proof of NP hardness of the Art Gallery Problem (which was described by Pritam last week). Approximation algorithms for the terrain guarding problem will also be described.

References: http://www.tcs.tifr.res.in/~ghosh/artgallery-approx.pdf