On the prize-collecting generalized minimum spanning tree problem |
| |
Authors: | P C Pop |
| |
Institution: | (1) Department of Mathematics and Computer Science, Faculty of Sciences, North University of Baia Mare, Baia Mare, Romania |
| |
Abstract: | The prize-collecting generalized minimum spanning tree problem (PC-GMSTP), is a generalization of the generalized minimum
spanning tree problem (GMSTP) and belongs to the hard core of -hard problems. We describe an exact exponential time algorithm for the problem, as well we present several mixed integer and integer
programming formulations of the PC-GMSTP. Moreover, we establish relationships between the polytopes corresponding to their
linear relaxations and present an efficient solution procedure that finds the optimal solution of the PC-GMSTP for graphs
with up 240 nodes. |
| |
Keywords: | Combinatorial optimization Minimum spanning trees Generalized minimum spanning tree problem Linear relaxation |
本文献已被 SpringerLink 等数据库收录! |
|