ScholarLens Back to search
2007•Unpublished venueRequires access

An Algorithm for Finding Minimum Degree Spanning Tree of Series-Parallel Graphs

Mohammad Atiqul Haque, Md. Reaz Uddin, Md. Abul Kashem

Open publisher page 0 citations

Abstract

A minimum degree spanning tree of a graph G is a spanning tree of G whose maximum degree is minimum among all spanning trees of G. The minimum degree spanning tree problem (MDST) is to construct such a spanning tree of a graph. In this paper, we propose a polynomial-time algorithm for solving the MDST problem on series-parallel graphs. Our algorithm runs in linear time for series-parallel graphs with small degrees. By applying this algorithm, we also give an approximation algorithm for solving the minimum edge-ranking spanning tree problem on series-parallel graphs.

About this research paper

What this paper is about

A minimum degree spanning tree of a graph G is a spanning tree of G whose maximum degree is minimum among all spanning trees of G. The minimum degree spanning tree problem (MDST) is to construct such a spanning tree of a graph. In this paper, we propose a polynomial-time algorithm for solving the MDST problem on series-parallel graphs. Our algorithm runs in linear time for series-parallel graphs with small degrees. By applying this algorithm, we also give an approximation algorithm for solving the minimum edge-ranking spanning tree problem on series-parallel graphs.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

A minimum degree spanning tree of a graph G is a spanning tree of G whose maximum degree is minimum among all spanning trees of G. The minimum degree spanning tree problem (MDST) is to construct such a spanning tree of a graph. In this paper, we propose a polynomial-time algorithm for solving the MDST problem on series-parallel graphs. Our algorithm runs in linear time for series-parallel graphs with small degrees. By applying this algorithm, we also give an approximation algorithm for solving the minimum edge-ranking spanning tree problem on series-parallel graphs.

Key concepts: Minimum spanning tree, Spanning tree, Kruskal's algorithm, k-minimum spanning tree, Distributed minimum spanning tree, Prim's algorithm, Euclidean minimum spanning tree, Reverse-delete algorithm

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
An Algorithm for Finding Minimum Degree Spanning Tree of Series-Parallel Graphs — Research Paper | ScholarLens