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

Authors

  • Razia Sultana Department of CSE, CIS and CS Daffodil International University, Dhaka

DOI:

https://doi.org/10.3329/diujst.v4i1.4347

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 log2 k(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
119
PDF
84

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.

Downloads

How to Cite

Sultana, R. (2010). 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

Issue

Vol. 4 No. 1 (2009)

Section

Papers

License

Copyright and Reprint Permissions
This journal and the individual contributions contained in it are protected by the copyright of Daffodil International University. Photocopies of this journal in full or parts for personal or classroom usage may be allowed provided that copies are not made or distributed for profit or commercial advantage and the copies bear this notice and the full citation. Copyright for components of this work owned by others than Daffodil International University must be honored. Abstracting with credit is permitted. Specific permission of the publisher and payment of a fee are required for multiple or systemic copying, copying for advertising or promotional purposes, resale, republishing, posting on servers, redistributing to lists and all forms of document delivery.

Subscribers may reproduce table of contents or prepare lists of articles including abstracts for internal circulation within their institutions. Permission of the publisher is required for resale and distribution outside the institution. Permission of the publisher is required for all other derivative works, including compilations and translations. Except as outlined above, no part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without prior written permission of the publisher.

Permissions may be sought directly from Daffodil International University; email: diujst@daffodilvarsity.edu.bd.