# The Minimum Weighted K-Tree Subgraph Problem ## Description:

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

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

Output:
-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

 TextBook Computers and Intractability: A Guide to the Theory of Np-Completeness by Michael R. Garey, David S. Johnson TextBook A memetic algorithm for the minimum weighted k-cardinality tree subgraph problem by Maria J. Blesa, Pablo Moscato, Fatos Xhafa TextBook How to Solve It: Modern Heuristics by Zbigniew Michalewicz, David B. Fogel TextBook New metaheuristic approaches for the edge-weighted k-cardinality tree problem (URL) by C. Blum, M. Blesa URL A compendium of NP optimization problems http://www.nada.kth.se/~viggo/problemlist/compendium.html URL Experiments for the Minimum Weighted K-Cardinality Tree Problem. MALLBA Project http://www.lsi.upc.es/~mallba/public/library/TabuSearch/minktree.html URL KCTLIB - A Library for the Edge-Weighted K-Cardinality Tree Problem http://iridia.ulb.ac.be/~cblum/kctlib/ Last Updated: 15/07/03                                                                                                                 For any question or suggestion, click here to contact with us.