An algorithm for solving minimum edge-ranking spanning tree problem on partial k-trees
DOI:
https://doi.org/10.3329/diujst.v4i1.4347Keywords:
Algorithm, partial k-trees, edge-ranking, spanning treeAbstract
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
119
84
Downloads
How to Cite
Issue
Section
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.