OR software - ORSEP operations research software exchange program Edited by Professor H.W. Hamacher K_TREE/K_SUBGRAPH: A program package for minimal weighted K-cardinality trees and subgraphs

摘要

The package is an implementation of several algorithms and heuristics for solving the minimal weighted K-cardinality tree and subgraph problem in undirected graphs with positive edge weights [3,4]. Applications of these problems are described in [6]. The algorithms are discussed in [3] as well as in [5]and [2]. In [3] extensive tests on the performance of the heuristics have been conducted, shoing e.g. the average deviation from the optimal solution si below one percent.