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

DOI10.1016/0166-218X(93)E0140-TzbMath0818.68095MaRDI QIDQ1805463

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) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Better approximations of non-Hamiltonian graphs ⋮ Approximation of coNP sets by NP-complete sets ⋮ Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of test case generation for NP-hard problems
• An introduction to the analysis of approximation algorithms
• Maximum number of edges in connected graphs with a given domination number
• A test problem generator for the Steiner problem in graphs
• On the theory of graphs

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