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

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