K-minimum spanning tree
http://dbpedia.org/resource/K-minimum_spanning_tree an entity of type: WikicatNP-hardProblems
The k-minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly k vertices and forms a subgraph of a larger graph. It is also called the k-MST or edge-weighted k-cardinality tree. Finding this tree is NP-hard, but it can be approximated to within a constant approximation ratio in polynomial time.
rdf:langString
rdf:langString
K-minimum spanning tree
xsd:integer
1152079
xsd:integer
1045360433
rdf:langString
The k-minimum spanning tree problem, studied in theoretical computer science, asks for a tree of minimum cost that has exactly k vertices and forms a subgraph of a larger graph. It is also called the k-MST or edge-weighted k-cardinality tree. Finding this tree is NP-hard, but it can be approximated to within a constant approximation ratio in polynomial time.
xsd:nonNegativeInteger
8374