We study the approximation ratios of several heuristics for NP-hard problems on graphs, with the ratios expressed as a function of some graph parameter. We obtain tight ratios as functions of these parameters by identifying the extremal graphs for these ratios.
Supervisor:
Prof. Jean Cardinal (ULB).