@techreport{
1999-TR4CBL-03-Gosh,
author = "D. Ghosh and F. Brglez and M. Stallmann",
title  = {Graph Mutants based on Characteristic Spanning Trees:
          Experimental Design of Heuristics for NP-Hard Problems},
institution = "{CBL, CS Dept., NCSU, Box 7550,
                Raleigh, NC 27695}",
number = "1999-TR4CBL-03-Gosh",
year   = "1999", 
note   = {Also available at
http://\-www.cbl.ncsu.edu/\-publications/},
abstract = "{
This paper introduces a comprehensive approach to the generation of random instances of graphs relevant to NP-hard problems in circuit design. Good experimental design techniques require that treatments (heuristics) be applied to a class of experimental subjects (graphs, circuits) that share common characteristics. Relevance is achieved only if these characteristics relate to the performance of heuristics on real circuits. We demonstrate that a characteristic spanning tree class of  a {\em reference graph} can be used to generate 
random graphs whose behavior with respect to various treatments is like that of the reference graph. Results for both graph crossing number and hypergraph partitioning are discussed. 
}"
}