|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
23 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Listing All Spanning Trees in Halin Graphs - Sequential and Parallel view | | K. Krishna Mohan Reddy
; P. Renjith
; N. Sadagopan
; | | Date: |
5 Nov 2015 | | Abstract: | For a connected labelled graph $G$, a {em spanning tree} $T$ is a connected
and an acyclic subgraph that spans all the 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})$. | | Source: | arXiv, 1511.1696 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER