Geodesic
Optimal edge ranking of complete bipartite graphs in polynomial time
Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 1, pp. 149-159

Voir la notice de l'article provenant de la source Library of Science

An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees and complete graphs, little has been known about special classes of graphs for which the problem can be solved in polynomial time. In this paper, we present a polynomial-time algorithm to find an optimal edge ranking for a complete bipartite graph by using the dynamic programming strategy.
Keywords: graph algorithms, edge ranking, vertex ranking, edge-separator tree, complete bipartite graphs 
@article{DMGT_2006_26_1_a13,
     author = {Hung, Ruo-Wei},
     title = {Optimal edge ranking of complete bipartite graphs in polynomial time},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {149--159},
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2006},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a13/}
}
TY  - JOUR
AU  - Hung, Ruo-Wei
TI  - Optimal edge ranking of complete bipartite graphs in polynomial time
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2006
SP  - 149
EP  - 159
VL  - 26
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a13/
LA  - en
ID  - DMGT_2006_26_1_a13
ER  - 
%0 Journal Article
%A Hung, Ruo-Wei
%T Optimal edge ranking of complete bipartite graphs in polynomial time
%J Discussiones Mathematicae. Graph Theory
%D 2006
%P 149-159
%V 26
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a13/
%G en
%F DMGT_2006_26_1_a13
Hung, Ruo-Wei. Optimal edge ranking of complete bipartite graphs in polynomial time. Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 1, pp. 149-159. http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a13/