AN ALGORITHM FOR SOLVING MINIMUM EDGE-RANKING SPANNING TREE PROBLEM ON PARTIAL K-TREES
| dc.contributor.author | Sultana, Razia | |
| dc.date.accessioned | 2012-11-08T10:29:13Z | |
| dc.date.accessioned | 2019-05-28T09:47:10Z | |
| dc.date.available | 2012-11-08T10:29:13Z | |
| dc.date.available | 2019-05-28T09:47:10Z | |
| dc.date.issued | 2009-01-01 | |
| dc.description.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. | |
| dc.identifier.other | http://dspace.daffodilvarsity.edu.bd:8080/handle/20.500.11948/481 | |
| dc.identifier.uri | http://hdl.handle.net/20.500.11948/481 | |
| dc.language.iso | en | |
| dc.publisher | Daffodil International University | |
| dc.source | DIU Institutional Repository | |
| dc.subject | Algorithm, partial k-trees, edge- ranking, spanning tree. | |
| dc.title | AN ALGORITHM FOR SOLVING MINIMUM EDGE-RANKING SPANNING TREE PROBLEM ON PARTIAL K-TREES | |
| dc.type | Article |
Files
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- An algorithm for solvingminimum.pdf.txt
- Size:
- 30.78 KB
- Format:
- Adobe Portable Document Format