A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs |
| |
Authors: | Shin-ichi Nakayama Shigeru Masuyama |
| |
Affiliation: | a The University of Tokushima, Department of Mathematical Sciences, Tokushima, Japan b Toyohashi University of Technology, Department of Knowledge-Based Information Engineering, Japan |
| |
Abstract: | An edge ranking of a graph G is a labeling r of its edges with positive integers such that every path between two different edges eu, ev with the same rank r(eu)=r(ev) contains an intermediate edge ew with rank r(ew)>r(eu). An edge ranking of G is minimum if the largest rank k assigned is the smallest among all rankings of G. The edge ranking problem is to find a minimum edge ranking of given graph G. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of trees. In this paper, we first show, on a general graph G, a relation between a minimum edge ranking of G and its minimal cuts, which ensures that we can obtain a polynomial time algorithm for obtaining minimum edge ranking of a given graph G if minimal cuts for each subgraph of G can be found in polynomial time and the number of those is polynomial. Based on this relation, we develop a polynomial time algorithm for finding a minimum edge ranking on a 2-connected outerplanar graph. |
| |
Keywords: | Algorithms Computational complexity Combinatorial problem Minimal cut Edge ranking |
本文献已被 ScienceDirect 等数据库收录! |
|