In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a minimum degree spanning tree is a subset of the edges of a
connected graph that connects all the
vertices together, without any
cycles, and its maximum degree of its vertices as small as possible. That is, it is a
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
whose maximum degree is minimal.
The decision problem is: Given a graph ''G'' and an integer ''k'', does ''G'' have a spanning tree such that no vertex has degree greater than ''k''? This is also known as the
degree-constrained spanning 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 spanni ...
problem.
Algorithms
Finding the minimum degree spanning tree of an undirected graph is
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
. This can be shown by reduction to the
Hamiltonian path problem
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a ...
. For directed graphs, finding the minimum degree spanning tree is also NP-hard.
R. Krishman and B. Raghavachari (2001) have a
quasi-polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
approximation algorithm to solve the problem for directed graphs.
M. Haque, Md. R. Uddin, and Md. A. Kashem (2007) found a
linear time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
algorithm that can find the minimum degree spanning tree of
series-parallel graphs with small degrees.
G. Yao, D. Zhu, H. Li, and S. Ma (2008) found a
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
algorithm that can find the minimum degree spanning tree of
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
s.
References
{{reflist
Spanning tree