The Minimum Weighted KTree Subgraph Problem


Description:The KTree problem is a classified NPhard optimization problem. It can be defined as: Input: Output: 

Statement of the ProblemThe minimum weighted kcardinality 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 ktrees that are subgraphs of G. This is a strongly NPHard combinatorial optimization problem. This said, it is unlikely to be solved by a polynomialtime 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


