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

DOI10.1016/0166-218X(93)E0140-TMaRDI QIDQ1805463zbMATH OpenFDO

Authors Laura A. Sanchis

Publication date 17 May 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-hard problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On the complexity of test case generation for NP-hard problems
• Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem
• scientific article; zbMATH DE number 1332677
• Evolving test instances of the Hamiltonian completion problem

Cites work

• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 742902 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 861339 (Why is no real title available?)
• scientific article; zbMATH DE number 3221976 (Why is no real title available?)
• A test problem generator for the Steiner problem in graphs
• An introduction to the analysis of approximation algorithms
• Maximum number of edges in connected graphs with a given domination number
• On the complexity of test case generation for NP-hard problems
• On the theory of graphs

Cited in

(5)

• Better approximations of non-Hamiltonian graphs
• Evolving test instances of the Hamiltonian completion problem
• Approximation of coNP sets by NP-complete sets
• On the complexity of test case generation for NP-hard problems
• Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs

This page was built for publication: Generating hard and diverse test sets for NP-hard graph problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1805463)