=Paper=
{{Paper
|id=Vol-2113/paper1
|storemode=property
|title=On the maximal number of leaves in induced subtrees of series-parallel graphs
|pdfUrl=https://ceur-ws.org/Vol-2113/paper1.pdf
|volume=Vol-2113
|authors=Moussa Abdenbi,Alexandre Blondin Massé,Alain Goupil
|dblpUrl=https://dblp.org/rec/conf/gascom/AbdenbiMG18
}}
==On the maximal number of leaves in induced subtrees of series-parallel graphs==
https://ceur-ws.org/Vol-2113/paper1.pdf
On the maximal number of leaves in induced subtrees
of series-parallel graphs
Moussa Abdenbi Alexandre Blondin Massé
Laboratoire de combinatoire et Laboratoire de combinatoire et
d’informatique mathématique d’informatique mathématique
Université du Québec à Montréal Université du Québec à Montréal
abdenbi.moussa@courrier.uqam.ca blondin masse.alexandre@uqam.ca
Alain Goupil
Université du Québec à Trois-Rivières
Alain.Goupil@uqtr.ca
Abstract
Given any simple graph G on n vertices and a positive integer i ≤ n,
an induced subtree of size i of G is called fully leafed if it has the
maximum number of leaves among all induced subtrees of the same
size. It has recently been proved that the problem FLIS of finding fully
leafed induced subtrees is NP-hard for general graphs. In this extended
abstract, we provide recursive formulas to compute the number of leaves
in fully leafed induced subtrees appearing in series-parallel graphs. As
a byproduct, the problem FLIS is polynomial for this family of graphs.
1 Introduction
Given some finite or infinite simple graph G, the study of the subgraphs of G reveals remarkable properties
about the whole graph. For instance, it is well known that a graph is planar if and only if it does not contain
a subgraph that is a subdivision of the complete bipartite graph K3,3 or of the complete graph K5 [Kur30]. A
more general result, due to Robertson and Seymour, states that any family of graphs closed under minors can
be equivalently defined by forbidding some finite set of minors [RS04].
In the last 30 years, considerable attention has been devoted to subgraphs that are trees [ESS86, KW91,
PTX84, SW05, WAU14]. For instance, Erdős, Saks and Sós considered induced subtrees of maximal size,
proving in particular that the problem is NP-hard in general [ESS86]. Around the same time, Payan, Tchuente
and Xuong considered trees having many leaves [PTX84] and, in the same spirit, a few years later, Kleitman
and West investigated spanning trees with a maximum number of leaves [KW91].
The case of subgraphs that are trees is of particular interest in several fields [BCL05, Yam14, Zak02]. As an
example, spanning trees with many leaves turn out to be interesting candidates for minimal energy consumption
in wireless newtorks [BCL05]. In chemistry, the Wiener index of chemical trees can be computed from its subtrees
[Yam14]. Finally, in the data mining community, it is argued that knowledge can be extracted by inspecting
particular subtrees of forests [Zak02].
Copyright © by the paper’s authors. Copying permitted for private and academic purposes.
In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at
http://ceur-ws.org
24
s
s s s
s
t
t t t t
(a) (b) (c) (d) (e)
Figure 1: Series-parallel graphs. The source and sink are labelled by s and t. (a) A basic SP-graph. (b) A
SP-graph and (c) another SP-graph. (c) Their series composition and (d) their parallel composition. In (d) and
(e), the blue vertices are obtained by “merging” some vertices of the two graphs used in the composition.
We are particularly interested in the problem of enumerating fully leafed induced subtrees, i.e., induced
subtrees whose number of leaves is maximal with respect to all induced subtrees of the same size [BCGLNV17].
These combinatorial objects were studied both in the general case [BCGLNV17] and in the particular context of
tree-like polyforms and polycubes [BCGS17]. Unfortunately, the problem of finding fully leafed induced subtrees
is NP-hard in general [BCGLNV17]. One possible approach to tackle such problems consists of finding a natural
parameter that allows fixed parameter tractable algorithms.
We consider the case of series-parallel graphs (SP-graphs), for which the problem becomes polynomial. We
believe that the ideas presented below are an important step in designing a parametrized algorithm for solving
the problem in general. Additionally, since our algorithm is derived from recursive formulas, it also yield useful
insights on the shape of fully leafed induced subtrees in series-parallel graphs.
2 Preliminaries
We briefly recall some definitions from graph theory. See [Die10] for more details. Unless otherwise stated, all
graphs considered in this text are undirected.
A graph is an ordered pair G = (V, E), where V is its set of vertices and E is its set of edges. Given a vertex
u, we denote by NG (u) the set of neighbors of u in G, i.e., NG (u) = {v ∈ V | {u, v} ∈ E}. When the context is
clear, we omit the index G and write simply N (u). The degree of u is defined by deg(u) = |N (u)|. The size of
G, denoted by |G|, is the total number |V | of vertices. For U ⊆ V , the subgraph of G induced by U , denoted by
G[U ], is the graph G[U ] = (U, E ∩ P2 (U )), where P2 (U ) is the set of all subsets of size 2 of U .
A graph is called a tree if it is both connected and acyclic. A vertex u ∈ V is called a leaf of T if deg(u) = 1.
The number of leaves of T is denoted by |T |l . We say that G[U ] is an induced subtree of G if the graph
induced by U is a tree. Forests and induced subforests are defined similarly by keeping the “acyclic” property
and removing the “connected” one.
A two-terminal graph is a quadruple G = (V, E, s, t), where (V, E) is a graph and s, t ∈ V , s 6= t, we call s
the source and t the sink of G. A two-terminal graph G = (V, E, s, t) is called a series-parallel graph (or simply
SP-graph) if one of the following three conditions is satisfied:
(i) (Basic SP-graph) V = {s, t} and E = {{s, t}};
(ii) (Series composition) There exist two SP-graphs G1 = (V1 , E1 , s1 , t1 ) and G2 = (V2 , E2 , s2 , t2 ) such that
V = V1 ∪ V2 , V1 ∩ V2 = {t1 } = {s2 }, E = E1 ∪ E2 , E1 ∩ E2 = ∅, s = s1 and t = t2 . In this case, we write
G = G1 ./ G2 .
(iii) (Parallel composition) There exist two SP-graphs G1 = (V1 , E1 , s, t) and G2 = (V2 , E2 , s, t), where at least
one graph among G1 , G2 is non basic, such that V = V1 ∪V2 , V1 ∩V2 = {s, t}, E = E1 ∪E2 and E1 ∩E2 = ∅.
In this case, we write G = G1 k G2 .
Examples of SP-graphs are depicted in Figure 1. Series-parallel graphs have been studied since the 19th
century. Their enumeration was investigated in 1890 by MacMahon [Mac90] and can be found in OEIS as
sequence A000084. A few years later, Riordan and Shannon [RS42] provided a formal proof of the recursive
25
(a) (b) (c)
Figure 2: Instances of the leaf induced subtree problem. (a) With i = 7 vertices and ` = 5 leaves. (b) With
i = 11 vertices and ` = 6 leaves. (c) A subtree that is not induced.
i 2 3 4 5 6 7 8 9 10 11 12 13 14 15
LG (i) 2 2 3 4 4 5 5 5 5 6 −∞ −∞ −∞ −∞
Table 1: Leaf function of the SP-graph of Figure 2.
formula given by MacMahon. From there, several papers have been published on their combinatorial properties
(see for instance [Fin03] and references therein).
3 Fully Leafed Induced Subtrees
As mentioned in the introduction, we are interested in induced subtrees of series-parallel graphs and in particular
those with several leaves. We first recall a definition introduced in [BCGLNV17].
Definition 3.1 (Leaf function, [BCGLNV17]). Given a finite or infinite graph G = (V, E), let TG (i) be the
family of all induced subtrees of G with exactly i vertices. The leaf function of G, denoted by LG , is the function
with domain {0, 1, 2, . . . , |G|} defined by
LG (i) = max{|T |l : T ∈ TG (i)},
with the convention max ∅ = −∞. An induced subtree T of G with i vertices is called fully leafed when
|T |l = LG (i).
The following problem was considered.
Problem 3.2 (Leaf Induced Subtree Problem, [BCGLNV17]). Given a simple graph G and two positive integers
i and `, does there exist an induced subtree of G with i vertices and ` leaves?
Example 3.3. Let G be the SP-graph illustrated in Figure 2. Positive instances of Problem 3.2 are identified
in (a) and (b). It is not hard to prove that both subtrees are fully leafed. More precisely, one can show that
(7, `) is a negative instance of Problem 3.2 for any ` > 5. Similarly, (11, `) is a negative instance of Problem 3.2
for any ` > 6. Notice that the adjective “induced” is important. For example, the blue subgraph illustrated in
Figure 2(c) is a subtree, but it is not induced for otherwise the dashed edge would have to be included, therefore
creating a cycle. Exhaustive inspection of all induced subtrees show that the leaf function of G is given by
Table 1.
4 Main Result
Let G be any SP-graph. We are interested in computing the leaf function LG of G. An important observation
is that induced subtrees of SP-graphs obtained by a parallel composition could be obtained by “merging” an
induced subforest with an induced subtree, i.e., a subtree in a graph and a forest in the other, which is not
intuitive. Fortunately, such a subforest factor has a very specific shape: it always has two connected components
and it must include both the source and the sink of the SP-graph in which it lives. Hence, we can restrict our
attention to those two types of induced subgraphs. Moreover, the following lemma, whose proof is omitted due
to lack of space, is key in describing the recursive formulas.
26
Lemma 4.1. Let G be a parallel or series composition of two SP-graphs G1 and G2 . If T = T1 ∪ T2 is a fully
leafed induced subtree or subforest of G, where T1 ⊆ G1 and T2 ⊆ G2 , then T1 and T2 are fully leafed induced
subtrees or subforests of G1 and G2 respectively.
Hence, by Lemma 4.1, we only need to keep track of the induced subtrees obtained by series or parallel
compositions and encode their status (leaf or inner vertex and proximity) with respect to the source and the
sink.
Definition 4.2. Let G = (V, E, s, t) be an SP-graph and i an integer, with 2 ≤ i ≤ |G|. We denote by L(G, i, σ, τ )
the maximum number of leaves that can be realized by an induced subtree T of size i of G, such that
0, if s ∈ T, degT (s) > 1;
0, if t ∈ T, degT (t) > 1;
1, if s ∈ T, degT (s) = 1; 1, if t ∈ T, degT (t) = 1;
σ= and τ =
2, if s ∈
/ T, |N (s) ∩ T | 6
= 0;
2, if t ∈
/ T, |N (t) ∩ T | =
6 0;
3, if s ∈
/ T, |N (s) ∩ T | = 0, 3, if t ∈
/ T, |N (t) ∩ T | = 0.
Similarly, let F (G, i, σ, τ ) be the maximum number of leaves that can be realized by an induced subforest of size
i whose two connected components Ts and Tt containing s and t respectively are such that
0, if degTs (s) > 1; 0, if degTt (t) > 1;
σ= and τ =
1, if degTs (s) = 1, 1, if degTt (t) = 1.
Clearly, the leaf function LG of G satisfies
LG (i) = max L(G, i, σ, τ ), (1)
0≤σ,τ ≤3
for i = 2, 3, . . . , |G|. Therefore, it is sufficient to describe how to compute recursively L(G, i, σ, τ ) and F (G, i, σ, τ )
to solve Problem 3.2 in the case of series-parallel graphs.
There are two additional useful definitions that we need to introduce. First, let DistN = {2, 3} × {2, 3} ∪
{0, 1}×{3}∪{3}×{0, 1}. Intuitively, when (σ, τ ) ∈ DistN, we are guaranteed that the composition of the induced
subtrees/subforests involved will not create a cycle because their respective vertices are “distant”. Moreover, for
(a, b) ∈ {0, 1} × {0, 1}, let ` be the leaf loss function defined by `(a, b) = a + b which indicates the number of
leaves that are lost after a composition. For the remainder of this section, we study the different cases, according
to the type of composition, in the case of induced subtrees as well as induced subforests.
4.1 Series composition
Assume that G = G1 ./ G2 , where G = (V, E, s, t), G1 = (V1 , E1 , s1 , t1 ), G2 = (V2 , E2 , s2 , t2 ). Also, let T be a
fully leafed induced subtree of G. There are three cases to consider.
(ST1) T is included in G1 . Then we define ST1 (G, i, σ, τ ) as the number of leaves of T :
ST1 (G, i, σ, τ ) = L(G1 , i, σ, τ1 ),
where (
2, if {s, t} ∈ E2 and τ1 ∈ {0, 1};
τ=
3, otherwise.
(ST2) T is included in G2 . Then we define ST2 (G, i, σ, τ ) as the number of leaves of T :
ST2 (G, i, σ, τ ) = L(G2 , i, σ2 , τ )
where (
2, if {s, t} ∈ E1 and σ2 ∈ {0, 1};
σ=
3, otherwise.
(ST3) T is included neither in G1 nor G2 . Then there exist a fully leafed induced subtree T1 of G1 and a
fully leafed induced subtree T2 of G2 such that T = T1 ∪ T2 and T1 ∩ T2 = {t1 } = {s2 }. Therefore, the number
of leaves of T is
ST3 (G, i, σ, τ ) = max {L(G1 , i1 , σ, τ1 ) + L(G2 , i2 , σ2 , τ ) − `(τ1 , σ2 )}
(i1 ,i2 )`i+1
τ1 ,σ2 ∈{0,1}
27
Combining the three cases, we have
L(G, i, σ, τ ) = max {STj (G, i, σ, τ )} (2)
j∈{1,2,3}
Now, assume that F is a fully leafed induced subforest of G whose two connected components are Ts and Tt ,
with s ∈ Ts and t ∈ Tt . Once again, we have three cases to consider.
(SF1) Ts is included in G1 and Tt is included in G2 . Then the number of leaves of F is
SF1 (G, i, σ, τ ) = max {L(G1 , i1 , σ, τ1 ) + L(G2 , i2 , σ2 , τ )}
(i1 ,i2 )`i
(τ1 ,σ2 )∈DistN
(SF2) Ts sticks out of G1 in G2 and Tt is included in G2 . Then
SF2 (G, i, σ, τ ) = max {L(G1 , i1 , σ, τ1 ) + F (G2 , i2 , σ2 , τ ) − `(τ1 , σ2 )}
(i1 ,i2 )`i+1
τ1 ,σ2 ∈{0,1}
(SF3) Ts is included in G1 and Tt sticks out of G2 in G1 . In this case, the number of leaves of F is
SF3 (G, i, σ, τ ) = max {F (G1 , i1 , σ, τ1 ) + L(G2 , i2 , σ2 , τ ) − `(τ1 , σ2 )}
(i1 ,i2 )`i+1
τ1 ,σ2 ∈{0,1}
Combining all three cases, we obtain the expression
F (G, i, σ, τ ) = max {SFj (G1 ./ G2 , i, σ, τ )} (3)
j=1,2,3
4.2 Parallel composition
The parallel composition is more intricate, but all cases can be covered using a similar reasoning. Assume that
G = G1 k G2 , where G = (V, E, s, t), G1 = (V1 , E1 , s1 , t1 ), G2 = (V2 , E2 , s2 , t2 ).
As in the last subsection, we first consider the subtree case. Let T be a fully leafed induced subtree of G. We
distinguish six cases.
(PT1) T is included in G1 . Then the number of leaves of T is
P T1 (G, i, σ, τ ) = L(G1 , i, σ, τ )
(PT2) T is included in G2 . In that case, we obtain
P T2 (G, i, σ, τ ) = L(G2 , i, σ, τ )
In the following cases T lives both in G1 and G2 .
(PT3) s ∈ T and t ∈ / T . Then we have σ = 0, since s is an internal vertex of T . Therefore, the number of
leaves in that case is
P T3 (G, i, 0, τ ) = max {L(G1 , i1 , σ1 , τ1 ) + L(G2 , i2 , σ2 , τ2 ) − `(σ1 , σ2 )}
(i1 ,i2 )`i+1
σ1 ,σ2 ∈{0,1}
(τ1 ,τ2 )∈DistN
where τ = min{τ1 , τ2 }
(PT4) s ∈
/ T and t ∈ T . This case is analogous to (PT3), but now we have τ = 0 and
P T4 (G, i, σ, 0) = max {L(G1 , i1 , σ1 , τ1 ) + L(G2 , i2 , σ2 , τ2 ) − `(τ1 , τ2 )}
(i1 ,i2 )`i+1
τ1 ,τ2 ∈{0,1}
(σ1 ,σ2 )∈DistN
where σ = min{σ1 , σ2 }
(PT5) T can be decomposed in a forest F1 included in G1 and a tree T2 included in G2 . In this case, observe
that s, t ∈ F1 , T2 , which implies σ = 0 and τ = 0. Therefore, the number of leaves of T is
P T5 (G, i, 0, 0) = max {F (G1 , i1 , σ1 , τ1 ) + L(G2 , i2 , σ2 , τ2 )
(i1 ,i2 )`i+2
σ1 ,τ1 ,σ2 ,τ2 ∈{0,1}
28
−`(τ1 , τ2 ) − `(σ1 , σ2 )}
(PT6) T can be decomposed in a tree T1 included in G1 and a forest F2 included in G2 . This case is analogous
to (PT5) and we obtain
P T6 (G, i, 0, 0) = max {L(G1 , i1 , σ1 , τ1 ) + F (G2 , i2 , σ2 , τ2 )
(i1 ,i2 )`i+2
σ1 ,τ1 ,σ2 ,τ2 ∈{0,1}
−`(τ1 , τ2 ) − `(σ1 , σ2 )}
Combining all six cases, we deduce that
L(G, i, σ, τ ) = max {P Tj (G, i, σ, τ )} (4)
1≤j≤6
Finally, assume that F is a fully leafed induced forest of G = G1 k G2 and write F = F1 ∪ F2 (F1 and F2
possibly empty), where F1 is included in G1 and F2 is included in G2 .
There are nine cases.
(PF1) F2 = ∅. Then the number of leaves of F is
P F1 (G, i, σ, τ ) = F (G1 , i, σ, τ )
(PF2) F1 = ∅. Then
P F2 (G, i, σ, τ ) = F (G2 , i, σ, τ )
(PF3) F1 is a subforest, F2 a subtree and s ∈ F2 . Then
P F3 (G, i, 0, τ ) = max {F (G1 , i1 , σ1 , τ ) + L(G2 , i2 , σ2 , 3) − `(σ1 , σ2 )}
(i1 ,i2 )`i+1
σ1 ,σ2 ∈{0,1}
(PF4) F1 is a subforest, F2 a subtree and t ∈ F2 . Then
P F4 (G, i, σ, 0) = max {F (G1 , i1 , σ, τ1 ) + L(G2 , i2 , 3, τ2 ) − `(τ1 , τ2 )}
(i1 ,i2 )`i+1
τ1 ,τ2 ∈{0,1}
(PF5) F1 is a subtree, F2 a subforest and s ∈ F1 . Then
P F5 (G, i, 0, τ ) = max {L(G1 , i1 , σ1 , 3) + F (G2 , i2 , σ2 , τ ) − `(σ1 , σ2 )}
(i1 ,i2 )`i+1
σ1 ,σ2 ∈{0,1}
(PF6) F1 is a subtree, F2 a subforest and t ∈ F1 . Then
P F6 (G, i, σ, 0) = max {L(G1 , i1 , 3, τ1 ) + F (G2 , i2 , σ, τ2 ) − `(τ1 , τ2 )}
(i1 ,i2 )`i+1
τ1 ,τ2 ∈{0,1}
(PF7) Both F1 and F2 are subtrees, s ∈ F1 and t ∈ F2 . Then
P F7 (G, i, σ, τ ) = max {L(G1 , i1 , σ, 3) + L(G2 , i2 , 3, τ )}
(i1 ,i2 )`i
σ,τ ∈{0,1}
(PF8) Both F1 and F2 are subtrees, s ∈ F2 and t ∈ F1 . Then
P F8 (G, i, σ, τ ) = max {L(G1 , i1 , 3, τ ) + L(G2 , i2 , σ, 3)}
(i1 ,i2 )`i
σ,τ ∈{0,1}
(PF9) Finally, Both F1 and F2 are subforests. Then
P F9 (G, i, 0, 0) = max {F (G1 , i1 , σ1 , τ1 ) + F (G2 , i2 , σ2 , τ2 )
(i1 ,i2 )`i+2
σ1 ,τ1 ,σ2 ,τ2 ∈{0,1}
−`(σ1 , σ2 ) − `(τ1 , τ2 )}
To summarize,
F (G, i, σ, τ ) = max {P Fj (G, i, σ, τ )}
1≤j≤9
We have covered all possible cases. It only remains to describe the behavior of the basis cases.
29
s t
Figure 3: The smallest SP-graph containing a basic forest.
4.3 Basis cases
Let BT be the basic SP-graph (see Figure 1(a)). Then we have
(
2, if i = 2 and σ = τ = 1;
L(BT , i, σ, τ ) = (5)
−∞, otherwise.
Moreover, for any SP-graph G, we have
L(G, 2, 1, τ ) = L(G, 2, σ, 1) = 2 (6)
for any σ, τ ∈ {0, 1, 2, 3}.
Finally, let BF be the SP-graph of 5 vertices depicted in Figure 3 and F the induced subforest higlighted in
blue. Then (
4, if i = 4 and σ = τ = 1;
F (BF , i, σ, τ ) = (7)
−∞ otherwise.
Hence, for any SP-graph G 6= BF of size at most 5, for all i ∈ {2, 3, . . . , |G|} and σ, τ ∈ {0, 1}, we have
F (G, i, σ, τ ) = −∞ (8)
5 Concluding Remarks
The recursive formulas presented in this paper can be easily translated into a program that generates all fully
leafed induced subtrees of a given SP-graph. In the future, we are interested in investigating the enumerative
combinatorics of induced subtrees of SP-graphs.
References
[BCGS17] A. Blondin Massé, J. de Carufel, A. Goupil and M. Samson. Fully Leafed Tree-Like Polyominoes and
Polycubes. In: L. Brankovic, J. Ryan, W. F. Smyth (Eds.): Combinatorial Algorithms / 28th Inter-
national Workshop, IWOCA 2017, Newcastle, NSW, Australia, Lecture Notes in Computer Science,
10765:206–218, 2017.
[BCGLNV17] A. Blondin Massé, J. de Carufel, A. Goupil, M. Lapointe, E. Nadeau and É Vandomme. Fully
leafed induced subtrees. At https://arxiv.org/abs/1709.09808, 2018.
[BCL05] A. Boukerche, X. Cheng and J. Linus. A Performance Evaluation of a Novel Energy-Aware Data-Centric
Routing Algorithm in Wireless Sensor Networks. Wireless Networks, 11(5):619–635, 2005.
[Die10] R. Diestel. Graph theory. Graduate Texts in Mathematics, 173, Springer-Verlag Berlin Heidelberg 2014.
[Epp92] D. Eppstein. Parallel recognition of series-parallel graphs. Information and Computation, 98(1):41–55,
1992.
[ESS86] P. Erdős, M. Saks and V. T. Sós. Maximum induced trees in graphs. Journal of Combinatorial Theory.
Series B, 41(1):61–79, 1986.
[Fin03] S. Finch. Series-parallel networks. Technical report. Harvard University, 2003.
[KW91] D. J. Kleitman and D. B. West. Spanning trees with many leaves. SIAM Journal on Discrete Mathe-
matics., 4(1):99–106, 1991.
[Kur30] C. Kuratowski. Sur le problème des courbes gauches en Topologie. Fundamenta Mathematicae,
15(1):271–283, 1930.
30
[Mac90] P. A. MacMahon. Yoke-Chains and Multipartite Compositions in connexion with the Analytical forms
called “Trees”. Proceedings of the London Mathematical Society, 1(1):330–346, 1890.
[PTX84] C. Payan, M. Tchuente and N. H. Xuong. Arbres avec un nombre maximum de sommets pendants.
Discrete Mathematics, 49(3):267–273, 1984.
[RS42] J. Riordan and C. E. Shannon. The Number of Two-Terminal Series-Parallel Networks Journal of
Mathematics and Physics, 21(1-4):83–93, 1942.
[RS04] N. Robertson and P. D. Seymour. Graph Minors. XX. Wagner’s conjecture. Journal of Combinatorial
Theory, Series B, 92(2):325–357, 2004.
[SW05] L. A. Székely and H. Wang. Arbres avec un nombre maximum de sommets pendants. Discrete Mathe-
matics, 34(1):138–155, 2005.
[WAU14] K. Wasa, H. Arimura and T. Uno. Efficient enumeration of induced subtrees in a K-degenerate graph.
In: H.-K- Ahn, C.-S. Shin (Eds.): Algorithms and computation / 25th International Symposium,
ISAAC 2014, Jeonju, Korea, Lecture Notes in Computer Science 8889, Springer, Cham, 2014, pp.
94–102. Springer, Cham, 2014.
[Yam14] M. Yamuna. Wiener index of chemical trees from its subtree. Der Pharma Chemica, 6(5):235–242,
2014
[Zak02] M. J. Zaki. Efficiently Mining Frequent Trees in a Forest. Proceedings of the Eighth ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining. KDD ’02, pp. 71–80. ACM, 2002.
31