K-minimum spanning tree

In mathematics, the K-minimum spanning tree is a graph G that spans some K of N vertices in the input set S with the minimum total length. K is less than or equal to N. The K-MST does not have to be a subgraph of the minimum spanning tree (MST). This problem is also known as Edge-Weighted K-Cardinality Tree (KCT).

This problem is NP-hard.

Refer to KCTLIB for more information.

External links

• Minimum k-spanning tree in "A compendium of NP optimization problems"

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Spanning tree NP-hard problems Combinatorics stubs Wikimedia Foundation. 2010. Игры ⚽ Нужно решить контрольную? Paz Lenchantin USS Guavina (SS-362) Look at other dictionaries: Minimum spanning tree — The minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length. Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all… …   Wikipedia Minimum spanning tree-based segmentation — Contents 1 Image segmentation introduction 2 Motivation for graph based methods 3 From images to graphs 4 Minimum Spanning Tree segmentation algorithms …   Wikipedia Euclidean minimum spanning tree — The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of points in the plane (or more generally in Bbb{R}^n), where the weight of the edge between each pair of points is the distance between those two points. In simpler… …   Wikipedia Distributed minimum spanning tree — The distributed minimum spanning tree problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential… …   Wikipedia Minimum-Spanning-Tree-Heuristik — Die MST Heuristik (MST steht für minimal spanning tree bzw. minimaler Spannbaum) dient dazu, das metrische Problem des Handlungsreisenden (TSP) zu approximieren. Dabei geht man wie folgt vor: Erzeuge einen minimalen Spannbaum für den… …   Deutsch Wikipedia Spanning tree (mathematics) — In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some (or perhaps all) of the edges of G . Informally, a spanning tree of G is a selection of edges of G… …   Wikipedia Spanning Tree Protocol — Internet protocol suite Application layer BGP DHCP DNS FTP HTTP …   Wikipedia Spanning tree protocol — The Spanning Tree Protocol is an OSI layer 2 protocol that ensures a loop free topology for any bridged LAN. It is based on an algorithm invented by Radia Perlman while working for Digital Equipment Corporationcite… …   Wikipedia Spanning Tree — Ein Graph mit einem minimalen Spannbaum. Ein Spannbaum (auch aufspannender Baum oder manchmal spannender Baum genannt; englisch spanning tree) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten… …   Deutsch Wikipedia Minimum spanning tree — …   Википедия 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”