Name
Abstract | ||
|---|---|---|
A BC-tree (block-cutpoint-tree) is a tree (with at least two vertices) where the distance between any two leaves is even. Motivated from the study of the \"core\" of a graph, BC-trees form an interesting class of trees. We provide a comprehensive study of questions related to BC-trees. As the analogue of the study of extremal questions on subtrees of trees, we first characterize the general extremal trees that maximize or minimize the number of BC-subtrees or leaf-containing BC-subtrees. We further discuss the \"middle part\" of a tree with respect to the number of BC-subtrees, namely the BC-subtree-core that behaves in a rather different way than all previously known \"middle parts\" of a tree. Last but not least, fast algorithms are proposed (following similar ideas as those of the enumeration of subtrees) for enumerating various classes of BC-subtrees of a tree. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.tcs.2015.02.028 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
bc-subtrees,extremal trees,middle part,enumeration,block-cutpoint-tree,bicolorable tree | Journal | 580 |
Issue | ISSN | Citations |
C | 0304-3975 | 13 |
PageRank | References | Authors |
0.63 | 11 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yu Yang | 1 | 18 | 3.42 |
| Hongbo Liu | 2 | 1426 | 105.95 |
| Hua Wang | 3 | 18 | 2.40 |
| Scott Makeig | 4 | 40 | 2.81 |