DSpace Repository

# Approximation algorithm for edge-ranking of series-parallel graphs

 dc.contributor.advisor Mia, Dr. Md. Abul Kashem dc.contributor.author Tanzima Hashem dc.date.accessioned 2015-12-14T11:56:24Z dc.date.available 2015-12-14T11:56:24Z dc.date.issued 2006-06 dc.identifier.uri http://lib.buet.ac.bd:8080/xmlui/handle/123456789/1528 dc.description.abstract This thesis deals with an approximation algorithm for finding edge-rankings en_US of series-parallel graphs. 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. An edge-ranking is optimal if the least number of distinct labels among all possible edge-rankings are used by it. The edge-ranking problem is to find an optimal edge-ranking of a given graph. Analogously, the vertex-ranking problem can be defined. The edge-ranking problem of graphs has important applications like scheduling the parallel assembly of a complex multi-part product from its components and parallel computation. The edge-ranking problem is NP-complete for series-parallel graphs, that is, finding a polynomial-time algorithm for solving the edge-ranking problem on series-parallel graphs with unbounded maximum degree is unlikely. In this thesis, we present a linear-time algorithm for finding a 2-vertex-separator tree of a series-parallel graph G and a linear-time approximation algorithm for finding the edge-ranking of a given series-parallel graph G using the 2-vertex-separator tree of G. Obtaining t.he 2- vertex-separator tree of G immediately improves the running time of the known best algorithm t.hat finds an optimal vertex-ranking of a series-parallel graph. dc.language.iso en en_US dc.publisher Department of Computer Science and Engineering, BUET en_US dc.subject Algorithm - Edge - Ranking - Series - Parallel graphs en_US dc.title Approximation algorithm for edge-ranking of series-parallel graphs en_US dc.type Thesis-MSc en_US dc.contributor.id 040405015 P en_US dc.identifier.accessionNumber 102893 dc.contributor.callno 006.31/TAN/2006 en_US
﻿