Listing All Spanning Trees in Halin Graphs - Sequential and Parallel view
| Autor: | Reddy, K. Krishna Mohan, Renjith, P., Sadagopan, N. |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | For a connected labelled graph $G$, a {\em spanning tree} $T$ is a connected and an acyclic subgraph that spans all vertices of $G$. In this paper, we consider a classical combinatorial problem which is to list all spanning trees of $G$. A Halin graph is a graph obtained from a tree with no degree two vertices and by joining all leaves with a cycle. We present a sequential and parallel algorithm to enumerate all spanning trees in Halin graphs. Our approach enumerates without repetitions and we make use of $O((2pd)^{p})$ processors for parallel algorithmics, where $d$ and $p$ are the depth, the number of leaves, respectively, of the Halin graph. We also prove that the number of spanning trees in Halin graphs is $O((2pd)^{p})$. Comment: 13 pages, 5 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|