Article ID: | iaor1997940 |
Country: | Netherlands |
Volume: | 58 |
Issue: | 1 |
Start Page Number: | 35 |
End Page Number: | 66 |
Publication Date: | Mar 1995 |
Journal: | Discrete Applied Mathematics |
Authors: | Sanchis Laura A. |
Keywords: | graphs |
In evaluating the performance of approximation algorithms for NP-hard problems, it is often necessary to resort to empirical testing. In order to do such testing it is useful to have test instances of the problem for which the correct answer is known. The paper presents algorithms for efficiently generating test instances for some NP-hard graph problems in such a way that the sets of instances generated can be shown to be both diverse and computationally hard. The techniques used involve combining extremal graph theory results with NP-hardness reductions.