DSpace Repository

Approximation algorithm for edge-ranking of series-parallel graphs

Show simple item record

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 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. en_US
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

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search BUET IR

Advanced Search


My Account