Matches in DBpedia 2014 for { <http://dbpedia.org/resource/K-minimum_spanning_tree> ?p ?o. }
Showing items 1 to 23 of
23
with 100 items per page.
- K-minimum_spanning_tree abstract "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.The input to the problem consists of an undirected graph with weights on its edges, and a number k. The output is a tree with k vertices and k − 1 edges, with all of the edges of the output tree belonging to the input graph. The cost of the output is the sum of the weights of its edges, and the goal is to find the tree that has minimum cost.The k-MST problem has been shown to be NP-hard by a reduction from the Steiner tree problem.The best approximation known for the problem achieves an approximation ratio of 2, and is by Garg (2005). This approximation relies heavily on the primal-dual schema of Goemans & Williamson (1992). When the input consists of points in the Euclidean plane (any two of which can be connected in the tree with cost equal to their distance) there exists a polynomial time approximation scheme devised by Arora (1998).".
- K-minimum_spanning_tree wikiPageExternalLink kctlib.
- K-minimum_spanning_tree wikiPageExternalLink node71.html.
- K-minimum_spanning_tree wikiPageID "1152079".
- K-minimum_spanning_tree wikiPageRevisionID "582644474".
- K-minimum_spanning_tree hasPhotoCollection K-minimum_spanning_tree.
- K-minimum_spanning_tree subject Category:NP-hard_problems.
- K-minimum_spanning_tree subject Category:Spanning_tree.
- K-minimum_spanning_tree type Abstraction100002137.
- K-minimum_spanning_tree type Attribute100024264.
- K-minimum_spanning_tree type Condition113920835.
- K-minimum_spanning_tree type Difficulty114408086.
- K-minimum_spanning_tree type NP-hardProblems.
- K-minimum_spanning_tree type Problem114410605.
- K-minimum_spanning_tree type State100024720.
- K-minimum_spanning_tree comment "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.The input to the problem consists of an undirected graph with weights on its edges, and a number k.".
- K-minimum_spanning_tree label "K-minimum spanning tree".
- K-minimum_spanning_tree sameAs m.04brp6.
- K-minimum_spanning_tree sameAs Q6322849.
- K-minimum_spanning_tree sameAs Q6322849.
- K-minimum_spanning_tree sameAs K-minimum_spanning_tree.
- K-minimum_spanning_tree wasDerivedFrom K-minimum_spanning_tree?oldid=582644474.
- K-minimum_spanning_tree isPrimaryTopicOf K-minimum_spanning_tree.