Optimal edge ranking of complete bipartite graphs in polynomial time

Ruo-Wei Hung

Discussiones Mathematicae Graph Theory (2006)

  • Volume: 26, Issue: 1, page 149-159
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Ruo-Wei Hung. "Optimal edge ranking of complete bipartite graphs in polynomial time." Discussiones Mathematicae Graph Theory 26.1 (2006): 149-159. <http://eudml.org/doc/270676>.

@article{Ruo2006,
abstract = {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.},
author = {Ruo-Wei Hung},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph algorithms; edge ranking; vertex ranking; edge-separator tree; complete bipartite graphs; colouring; NP-complete},
language = {eng},
number = {1},
pages = {149-159},
title = {Optimal edge ranking of complete bipartite graphs in polynomial time},
url = {http://eudml.org/doc/270676},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Ruo-Wei Hung
TI - Optimal edge ranking of complete bipartite graphs in polynomial time
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 1
SP - 149
EP - 159
AB - 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.
LA - eng
KW - graph algorithms; edge ranking; vertex ranking; edge-separator tree; complete bipartite graphs; colouring; NP-complete
UR - http://eudml.org/doc/270676
ER -

References

top
  1. [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. 
  2. [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. Zbl0907.68137
  3. [3] C.C. Chou, C.M. Fu and W.C. Huang, Decomposition of K m , n into short cycles, Discrete Math. 197/198 (1999) 195-203. Zbl0934.05106
  4. [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. Zbl0463.05057
  5. [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. Zbl0826.68093
  6. [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. Zbl0941.05516
  7. [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. Zbl0937.68093
  8. [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. Zbl0867.05022
  9. [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. Zbl0867.05024
  10. [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. Zbl0727.05053
  11. [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. Zbl06590794
  12. [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. Zbl0902.68088
  13. [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. Zbl0984.68200
  14. [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. 
  15. [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. Zbl0906.68087
  16. [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. Zbl0675.90085
  17. [17] A. Pothen, The complexity of optimal elimination trees, Technical Report CS-88-13 (the Pennsylvania State University, 1988). 
  18. [18] A.A. Schäffer, Optimal node ranking of trees in linear time, Inform. Process. Lett. 33 (1989/1990) 91-96. Zbl0683.68038
  19. [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. 
  20. [20] J.D. Ullman, Computational aspects of VLSI (Computer Science Press, Rockville, MD, 1984). Zbl0539.68021
  21. [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. Zbl0847.05083

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.