Maximum Independent Set for Interval Graphs and Trees in Space Efficient Models.
Binay Kumar Bhattacharya, Minati De, Subhas Chandra Nandy, Sasanka Roy · Canadian Conference on Computational Geometry · 2014
Space ecient algorithms for the maximum independent set problem for interval graphs and trees are presented in this paper. For a given set of n intervals on a real line, we can compute the maximum independent set in O( n 2 s +n logs) time using O(s) extra-space. The lower bound of the time space product for this problem is ( n 2 ),