Department of
Electronics and Informatics
Optimization graph problems such as finding a maximum independent set, bandwidth and pagenumber are considered. In particular, we are investigating the inapproximability of the bandwidth problem, designing approximation algorithms for finding a weighted maximum independent set, and analyzing the approximability/nonapproximability of the pagenumber problem.