Listing all spanning trees in Halin graphs -- sequential and parallel view

DOI10.1142/S1793830918500052MaRDI QIDQ4603872zbMATH OpenOpenAlexFDO

Authors K. Krishna Mohan Reddy, P. Renjith, N. Sadagopan

Publication date 23 February 2018

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.01696

zbMATH Keywords

Halin graphsspanning tree enumeration

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: 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)$.

Recommendations

• scientific article; zbMATH DE number 2104719
• Publication:3484353
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• scientific article; zbMATH DE number 177570
• scientific article; zbMATH DE number 56828

Cites work

• A flexible algorithm for generating all the spanning trees in undirected graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• An algorithm for enumerating all spanning trees of a directed graph
• An Efficient Parallel Biconnectivity Algorithm
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Boxicity of Halin graphs
• Efficient enumeration of ordered trees with \(k\) leaves
• Efficient generation of plane trees.
• Efficient Planarity Testing
• EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
• Finding All Spanning Trees of Directed and Undirected Graphs
• scientific article; zbMATH DE number 3853133 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 2104719 (Why is no real title available?)
• Listing all Minimal Separators of a Graph
• On maximal independent sets of nodes in trees
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Testing bipartiteness of geometric intersection graphs
• The bridge-connectivity augmentation problem with a partition constraint
• VPG and EPG bend-numbers of Halin graphs

Cited in

(3)

• scientific article; zbMATH DE number 4155883 (Why is no real title available?)
• scientific article; zbMATH DE number 2104719 (Why is no real title available?)
• Generating spanning-tree sequences of a fan graph in lexicographic order and ranking/unranking algorithms

This page was built for publication: Listing all spanning trees in Halin graphs -- sequential and parallel view

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603872)