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: Output: |
||||||||||||||||
Statement of the ProblemThe 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 InstancesIn 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
|
||||||||||||||||
|