×

zbMATH — the first resource for mathematics

Optimal edge ranking of trees in polynomial time. (English) Zbl 0826.68093
Summary: An edge ranking of a graph is a labeling of the edges using positive integers such that all paths between two edges with the same label contain an intermediate edge with a higher label. An edge ranking is optimal if the highest label used is as small as possible. The edge- ranking problem has applications in scheduling the manufacture of complex multipart products; it is equivalent to finding the minimum height edge- separator tree. In this paper we give the first polynomial-time algorithm to find an optimal edge ranking of a tree, placing the problem in \({\mathcal P}\). An interesting feature of the algorithm is an usual greedy procedure that allows us to narrow an exponential search space down to a polynomial search space containing an optimal solution. An \({\mathcal {NC}}\) algorithm is presented that finds an optimal edge ranking for trees for constant degree. We also prove that a natural decision problem emerging from our sequential algorithm is \({\mathcal P}\)-complete.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. P. Brent, The parallel evaluation of general arithmetic expressions,Journal of the ACM,21 (1974), 201-206. · Zbl 0276.68010 · doi:10.1145/321812.321815
[2] R. Cole, Parallel merge sort,SIAM Journal on Computing,17 (1988), 770-785. · Zbl 0651.68077 · doi:10.1137/0217049
[3] P. de la Torre and R. Greenlaw, Super critical tree numbering and optimal tree ranking are in NC,Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, Dallas, TX, 1991, pp. 767-773.
[4] P. de la Torre, R. Greenlaw, and T. M. Przytycka, The optimal tree ranking problem is inNC,Parallel Processing Letters,2 (1992), 31-41. · doi:10.1142/S0129626492000155
[5] P. de la Torre, R. Greenlaw, and A. A. Schäffer, Optimal Edge Raking of Trees in Polynomial Time, Technical Report 92-10, University of New Hampshire, 1993.
[6] P. de la Torre, R. Greenlaw, and A. A. Schäffer, A Note on Deogun and Peng’s Edge Ranking Algorithm, Technical Report 93-13, University of New Hampshire, 1993.
[7] J. S. Deogun and Y. Peng, Edge ranking of trees,Congressus Numerantium,79 (1990), 19-28. · Zbl 0862.05025
[8] M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979. · Zbl 0411.68039
[9] L. M. Goldschlager, R. A. Shaw, and J. Staples, The maximum flow problem is log space complete forP Theoretical Computer Science,21 (1982), 105-111. · Zbl 0486.68035 · doi:10.1016/0304-3975(82)90092-5
[10] R. Greenlaw, H. J. Hoover, and W. L. Ruzzo,Limits to Parallel Computation: P-completeness Theory, Computing Science Series, editor Z. Galil, Oxford University Press, Oxford, 1995. · Zbl 0829.68068
[11] A. V. Iyer, H. D. Ratliff, and G. Vijayan, Optimal node ranking of trees,Information Processing Letters,28 (1988), 225-229. · Zbl 0661.68063 · doi:10.1016/0020-0190(88)90194-9
[12] A. V. Iyer, H. D. Ratliff, and G. Vijayan, On an edge ranking problem of trees and graphs,Discrete Applied Mathematics,30 (1991), 43-52. · Zbl 0727.05053 · doi:10.1016/0166-218X(91)90012-L
[13] J. M. Lewis and M. Yannakakis, The node-deletion problem for hereditary properties isNP-complete,Journal of Computer and System Sciences,20 (1980), 219-230. · Zbl 0436.68029 · doi:10.1016/0022-0000(80)90060-4
[14] Y. Liang, S. K. Dhall, and S. Lakshmivarahan, Parallel algorithms for ranking of trees,Proceedings of the Second Annual Symposium on Parallel and Distributed Computing, Dallas, TX, 1990, pp. 26-31.
[15] N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms,Journal of the ACM,30 (1983), 852-865. · Zbl 0627.68034 · doi:10.1145/2157.322410
[16] J. Nevins and D. Whitney, editors,Concurrent Design of Products and Processes, McGraw-Hill, New York, 1989.
[17] Y. Perl and S. Zaks, On the complexity of edge labelings for trees,Theoretical Computer Science,19 (1982), 1-16. · Zbl 0478.68069 · doi:10.1016/0304-3975(82)90011-1
[18] T. M. Przytycka, The optimal tree ranking problem is inNC Manuscript, 1991.
[19] A. A. Schäffer, Optimal node ranking of trees in linear time,Information Processing Letters,33 (1989/90), 91-96. · Zbl 0683.68038 · doi:10.1016/0020-0190(89)90161-0
[20] M. Yannakakis, Node-deletion problems on bipartite graphs,SIAM Journal on Computing,10 (1981), 310-327. · Zbl 0468.05044 · doi:10.1137/0210022
[21] M. Yannakakis, Edge-deletion problems,SIAM Journal on Computing,10 (1981), 297-309. · Zbl 0468.05043 · doi:10.1137/0210021
[22] X. Zhou and T. Nishizeki, An efficient algorithm for edge-ranking trees,Proceedings of the Second European Symposium on Algorithms, Utrecht, Lecture Notes in Computer Science, Volume 855, Springer-Verlag, Berlin, 1994, pp. 118-129.
[23] X. Zhou and T. Nishizeki, Finding optimal edge-rankings of trees,Proceedings of the Sixth Annual Symposium on Discrete Algorithms, San Francisco, CA, 1995, pp. 122-131. · Zbl 0847.05083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.