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.