flâneur

Degree-constrained spanning tree - Wikipedia

en.wikipedia.org · 529 words · saved by 1 readers

In graph theory, a degree-constrained spanning tree is a spanning tree where the maximum vertex degree is limited to a certain constant k. The degree-constrained spanning tree problem is to determine whether a particular graph has such a spanning tree for a particular k. Input: n-node undirected graph G(V,E); positive integer k < n. Question: Does G have a spanning tree in which no node has degree greater than k? This problem is NP-complete (Garey & Johnson 1979). This can be shown by a reduction from the Hamiltonian path problem. It remains NP-complete even if k is fixed to a value ≥ 2. If the problem is defined as the degree must be ≤ k, the k = 2 case of degree-confined spanning tree is the Hamiltonian path problem. On a weighted graph, a Degree-constrained minimum spanning tree (DCMST) is a degree-constrained spanning tree in which the sum of its edges has the minimum possible sum. Finding a DCMST is an NP-Hard problem.[1] Heuristic algorithms that can solve the problem in polynomi

Degree-constrained spanning tree - Wikipedia Jump to content From Wikipedia, the free encyclopedia Type of spanning tree A spanning tree can be constructed where the vertex with the highest degree is 3 (thus, a max degree 3 tree). In graph theory , a degree-constrained spanning tree is a spanning tree where the maximum vertex degree is limited to a certain constant k . The degree-constrained spanning tree problem is to determine whether a particular graph has such a spanning tree for a particular k . Formal definition [ edit ] Input: n -node undirected graph G(V,E); positive integer k < n . Qu

related reading