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 |
|
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.