An algorithm for solving minimum edge-ranking spanning tree problem on partial k-trees

  • Razia Sultana Department of CSE, CIS and CS Daffodil International University, Dhaka
Keywords: Algorithm, partial k-trees, edge-ranking, spanning tree

Abstract

An edge-ranking of a graph G is a labeling of its edges with positive integers such that every path between two edges with the same label i contains an intermediate edge with label j>i. The minimum edge-ranking spanning tree problem is to find a spanning tree of a graph G whose edge-ranking needs least number of ranks. In this paper, we present an algorithm to solve the minimum edge-ranking spanning tree problem on a partial k-tree G in O(n2Δ(k+1)+2 Δk(k+1)+2 log2k(k+1)+2n) time, where n is the number of vertices, Δ is the maximum vertex degree of the graph G and k is bounded by a constant value.

Keywords: Algorithm, partial k-trees, edge-ranking, spanning tree.

DOI: 10.3329/diujst.v4i1.4347

Daffodil International University Journal of Science and Technology Vol.4(1) 2009 pp.1-8

Downloads

Download data is not yet available.
Abstract
616
PDF
441

Author Biography

Razia Sultana, Department of CSE, CIS and CS Daffodil International University, Dhaka
Razia Sultana has completed her M.Sc. Engg. in Information and Communication Technology from Institute of Information and Communication Technology (IICT) of Bangladesh University of Engineering and Technology (BUET) and B.Sc. Engg. in Computer Science and Engineering from Rajshahi University of Engineering and Technology (RUET). Now she is working as Senior Lecturer in the Department of CSE, CIS & CS of Daffodil International University. Her topics of interest are Graph Theory, Bioinformatics, and Networking.
How to Cite
Sultana, R. (1). An algorithm for solving minimum edge-ranking spanning tree problem on partial k-trees. Daffodil International University Journal of Science and Technology, 4(1), 1-8. https://doi.org/10.3329/diujst.v4i1.4347
Section
Papers