Paper Info
Title
A test problem generator for the Steiner problem in graphs
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 solutions. The technique uses the KKT optimality conditions on the corresponding quadratically constrained optimization problem.
Year
DOI
Venue
1993
10.1145/168173.168420
ACM Trans. Math. Softw.
Keywords
Field
DocType
optimal solution,integer programming,corresponding quadratically,test problem generator,steiner problem,optimization problem,test problems,steiner problem in graphs,new binary-programming formulation,kkt optimality condition,test problem
Graph,Mathematical optimization,Quadratic growth,Steiner tree problem,Integer programming,Constrained optimization problem,Karush–Kuhn–Tucker conditions,Mathematics
Journal
Volume
Issue
ISSN
19
4
0098-3500
Citations 
PageRank 
References 
18
2.28
11
Authors
3
Name
Order
Citations
PageRank
B. N. Khoury1303.73
Panos M. Pardalos269898.99
D.-Z. Du321952.53