Generating hard and diverse test sets for NP-hard graph problems

Generating hard and diverse test sets for NP-hard graph problems

0.00 Avg rating0 Votes
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:
Keywords: graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.