Title :
An Algorithm for Finding Minimum Degree Spanning Tree of Series-Parallel Graphs
Author :
Haque, Mohammad Atiqul ; Uddin, Reaz ; Kashem, Abul
Author_Institution :
Bangladesh Univ. of Eng. & Technol., Dhaka
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.
Keywords :
graph theory; minimum degree spanning tree; minimum edge-ranking spanning tree problem; polynomial-time algorithm; series-parallel graphs; Approximation algorithms; Communications technology; Computer science; Labeling; Lagrangian functions; Polynomials; Power grids; Power system dynamics; Steiner trees; Tree graphs; Algorithm; Edge-ranking; Series-parallel graph; Spanning tree;
Conference_Titel :
Information and Communication Technology, 2007. ICICT '07. International Conference on
Conference_Location :
Dhaka
Print_ISBN :
984-32-3394-8
DOI :
10.1109/ICICT.2007.375336