The Minimum Weighted K-Tree Subgraph Problem



The K-Tree problem is a classified NP-hard optimization problem. It can be defined as:

-An undirected graph G=(V,E).
-Weight function .
-An integer K.

-A subgraph's tree of G with K vertexs.



Statement of the Problem

The minimum weighted k-cardinality tree subgraph problem consists in finding, in a given undirected graph G=(V,E) a tree of k edges having minimal total weight among all of k-trees that are subgraphs of G. This is a strongly NP-Hard combinatorial optimization problem. This said, it is unlikely to be solved by a polynomial-time algorithm.


Problem Instances

In order to define an instance of this problem we need to provide all the information about the Graph. This means: his Vertex Set and the associated Edge Set between pairs of vertexs. The edges are weighted, so we have to indicate this value for each one.


Related Bibliography and Papers

Computers and Intractability: A Guide to the Theory of Np-Completeness
by Michael R. Garey, David S. Johnson

A memetic algorithm for the minimum weighted k-cardinality tree subgraph problem
by Maria J. Blesa, Pablo Moscato, Fatos Xhafa

How to Solve It: Modern Heuristics
by Zbigniew Michalewicz, David B. Fogel
New metaheuristic approaches for the edge-weighted k-cardinality tree problem (URL)
by C. Blum, M. Blesa
A compendium of NP optimization problems
Experiments for the Minimum Weighted K-Cardinality Tree Problem. MALLBA Project
KCTLIB - A Library for the Edge-Weighted K-Cardinality Tree Problem

Last Updated: 15/07/03                                                                                                                 For any question or suggestion, click here to contact with us.