TY - GEN
T1 - On the Number of Steiner Trees in a Graph
AU - Sen, A.
AU - Zhou, C.
AU - Mazumder, A.
AU - Das, A.
AU - Basu, K.
AU - Walkowiak, K.
N1 - Publisher Copyright:
© 2020 IEEE.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/3
Y1 - 2020/3
N2 - In a number of networking problems, one needs to find multiple paths between a source-destination node pair or multiple trees spanning all (or some of) the nodes of the network. Accordingly, a number of algorithms for generating (i) k shortest paths between a specified source-destination node pair, (ii) k Spanning trees, (iii) k Steiner trees, etc. are used in networking literature. However, any network G = (V, E) will have a specific number of Spanning Trees. Suppose that for a given network this number is p. In case if one attempts to create k Spanning Trees where k > p, the effort will end up in failure, as k Spanning trees do not exist for the network. Thus, before embarking of creating k Spanning trees, one needs to make sure that k < p. In case of Spanning trees, it is easy to verify that k < p, as Cayley's formula provides the number of labeled Spanning Trees of a complete graph. However, if one wants to generate multiple trees spanning only a specified subset of nodes, Cayley's formula will not be helpful, as in this case one needs to create Steiner trees by connecting the specified subset of nodes. The goal of this paper is to find a counterpart of Cayley's formula for the Steiner trees. To the best of our knowledge, no such formula is known for the number of Steiner Trees in a complete graph with n nodes and p terminal nodes. In this paper, we first provide a formula for the number of Steiner Trees of a complete graph, when p = 2 and p = 3. For p ≥ 4 we provide two algorithms, of which the first one computes the number of Steiner Trees, and the second one generates all the Steiner Trees of a complete graph with n nodes and p terminal nodes. The complexity of the first algorithm is O(np) and the second algorithm generates a Steiner Tree every O(n) unit of delay. It may be noted that the second algorithm can be used for any graphs, not only for the complete graphs.
AB - In a number of networking problems, one needs to find multiple paths between a source-destination node pair or multiple trees spanning all (or some of) the nodes of the network. Accordingly, a number of algorithms for generating (i) k shortest paths between a specified source-destination node pair, (ii) k Spanning trees, (iii) k Steiner trees, etc. are used in networking literature. However, any network G = (V, E) will have a specific number of Spanning Trees. Suppose that for a given network this number is p. In case if one attempts to create k Spanning Trees where k > p, the effort will end up in failure, as k Spanning trees do not exist for the network. Thus, before embarking of creating k Spanning trees, one needs to make sure that k < p. In case of Spanning trees, it is easy to verify that k < p, as Cayley's formula provides the number of labeled Spanning Trees of a complete graph. However, if one wants to generate multiple trees spanning only a specified subset of nodes, Cayley's formula will not be helpful, as in this case one needs to create Steiner trees by connecting the specified subset of nodes. The goal of this paper is to find a counterpart of Cayley's formula for the Steiner trees. To the best of our knowledge, no such formula is known for the number of Steiner Trees in a complete graph with n nodes and p terminal nodes. In this paper, we first provide a formula for the number of Steiner Trees of a complete graph, when p = 2 and p = 3. For p ≥ 4 we provide two algorithms, of which the first one computes the number of Steiner Trees, and the second one generates all the Steiner Trees of a complete graph with n nodes and p terminal nodes. The complexity of the first algorithm is O(np) and the second algorithm generates a Steiner Tree every O(n) unit of delay. It may be noted that the second algorithm can be used for any graphs, not only for the complete graphs.
UR - http://www.scopus.com/inward/record.url?scp=85085496199&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85085496199&partnerID=8YFLogxK
U2 - 10.1109/DRCN48652.2020.1570613458
DO - 10.1109/DRCN48652.2020.1570613458
M3 - Conference contribution
AN - SCOPUS:85085496199
T3 - 2020 16th International Conference on the Design of Reliable Communication Networks, DRCN 2020
BT - 2020 16th International Conference on the Design of Reliable Communication Networks, DRCN 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 16th International Conference on the Design of Reliable Communication Networks, DRCN 2020
Y2 - 25 March 2020 through 27 March 2020
ER -