Optimal edge ranking of complete bipartite graphs in polynomial time
Ruo-Wei Hung
Discussiones Mathematicae Graph Theory, Tome 26 (2006), p. 149-159 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2006-01-01
EUDML-ID : urn:eudml:doc:270676 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1309,
     author = {Ruo-Wei Hung},
     title = {Optimal edge ranking of complete bipartite graphs in polynomial time},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {26},
     year = {2006},
     pages = {149-159},
     zbl = {1104.05065},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1309}
}

Ruo-Wei Hung. Optimal edge ranking of complete bipartite graphs in polynomial time. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 149-159. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1309/

[000] [1] B. Aspvall and P. Heggernes, Finding minimum height elimination trees for interval graphs in polynomial time, BIT 34 (1994) 484-509, doi: 10.1007/BF01934264.

[001] [2] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller and Z. Tuza, Rankings of graphs, SIAM J. Discrete Math. 11 (1998) 168-181, doi: 10.1137/S0895480195282550. | Zbl 0907.68137

[002] [3] C.C. Chou, C.M. Fu and W.C. Huang, Decomposition of Km,n into short cycles, Discrete Math. 197/198 (1999) 195-203. | Zbl 0934.05106

[003] [4] D.G. Corneil, H. Lerchs and L.K. Stewart, Complement reducible graphs, Discrete Appl. Math. 3 (1981) 163-174, doi: 10.1016/0166-218X(81)90013-5. | Zbl 0463.05057

[004] [5] P. De La Torre, R. Greenlaw and A.A. Schaffer, Optimal edge ranking of trees in polynomial time, Algorithmica 13 (1995) 592-618, doi: 10.1007/BF01189071. | Zbl 0826.68093

[005] [6] J.S. Deogun, T. Kloks, D. Kratsch and H. Müller, On vertex ranking for permutation and other graphs, Lecture Notes in Comput. Sci. 775 (Springer-Verlag, 1994) 747-758. | Zbl 0941.05516

[006] [7] J.S. Deogun, T. Kloks, D. Kratsch and H. Müller, On vertex ranking for trapezoid, circular-arc and other graphs, Discrete Appl. Math. 98 (1999) 39-63, doi: 10.1016/S0166-218X(99)00179-1. | Zbl 0937.68093

[007] [8] P.E. Haxell, Partitioning complete bipartite graphs by monochromatic cycles, J. Combin. Theory (B) 69 (1997) 210-218, doi: 10.1006/jctb.1997.1737. | Zbl 0867.05022

[008] [9] A.A. Ivanov, R.A. Liebler, T. Penttila and C.E. Praeger, Antipodal distance-transitive covers of complete bipartite graphs, Europ. J. Combinatorics 18 (1997) 11-33, doi: 10.1006/eujc.1993.0086. | Zbl 0867.05024

[009] [10] A.V. Iyer, H.D. Ratliff and G. Vijayan, On an edge ranking problem of trees and graphs, Discrete Appl. Math. 30 (1991) 43-52, doi: 10.1016/0166-218X(91)90012-L. | Zbl 0727.05053

[010] [11] T. Kloks, H. Müller and C.K. Wong, Vertex ranking of asteroidal triple-free graphs, Inform. Process. Lett. 68 (1989) 201-206, doi: 10.1016/S0020-0190(98)00162-8. | Zbl 06590794

[011] [12] T.W. Lam and F.L. Yue, Edge ranking of graphs is hard, Discrete Appl. Math. 85 (1998) 71-86, doi: 10.1016/S0166-218X(98)00029-8. | Zbl 0902.68088

[012] [13] T.W. Lam and F.L. Yue, Optimal edge ranking of trees in linear time, Algorithmica 30 (2001) 12-33, doi: 10.1007/s004530010076. | Zbl 0984.68200

[013] [14] C.E. Leiserson, Area efficient graph layouts for VLSI, in: Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science FOCS'80 (1980) 270-281.

[014] [15] C.M. Liu and M.S. Yu, An optimal parallel algorithm for node ranking of cographs, Discrete Appl. Math. 87 (1998) 187-201, doi: 10.1016/S0166-218X(98)00056-0. | Zbl 0906.68087

[015] [16] D.C. Llewellyn, C. Tovey and M. Trick, Local optimization on graphs, Discrete Appl. Math. 23 (1989) 157-178, doi: 10.1016/0166-218X(89)90025-5. | Zbl 0675.90085

[016] [17] A. Pothen, The complexity of optimal elimination trees, Technical Report CS-88-13 (the Pennsylvania State University, 1988).

[017] [18] A.A. Schäffer, Optimal node ranking of trees in linear time, Inform. Process. Lett. 33 (1989/1990) 91-96. | Zbl 0683.68038

[018] [19] P. Scheffler, Node ranking and searching on graphs (Abstract), in: U. Faigle and C. Hoede (eds.), 3rd Twente Workshop on Graphs and Combinatorial Optimization, Memorandum No. 1132, Faculty of Applied Mathematics, University of Twente, The Netherlands, 1993.

[019] [20] J.D. Ullman, Computational aspects of VLSI (Computer Science Press, Rockville, MD, 1984). | Zbl 0539.68021

[020] [21] X. Zhou and T. Nishizeki, Finding optimal edge rankings of trees, in: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms SODA'95 (1995) 122-131. | Zbl 0847.05083