A TEST PROBLEM GENERATOR FOR THE STEINER PROBLEM IN GRAPHS

Citation
Bn. Khoury et al., A TEST PROBLEM GENERATOR FOR THE STEINER PROBLEM IN GRAPHS, ACM transactions on mathematical software, 19(4), 1993, pp. 509-522
Citations number
23
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Sciences",Mathematics
ISSN journal
0098-3500
Volume
19
Issue
4
Year of publication
1993
Pages
509 - 522
Database
ISI
SICI code
0098-3500(1993)19:4<509:ATPGFT>2.0.ZU;2-3
Abstract
In this paper we present a new binary-programming formulation for the Steiner problem in graphs (SPG), which is well known to be NP-hard. We use this formulation to generate test problems with known optimal sol utions. The technique uses the KKT optimality conditions on the corres ponding quadratically constrained optimization problem.