{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T04:57:35Z","timestamp":1768280255813,"version":"3.49.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1007\/bf01189071","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T22:39:28Z","timestamp":1108679968000},"page":"592-618","source":"Crossref","is-referenced-by-count":45,"title":["Optimal edge ranking of trees in polynomial time"],"prefix":"10.1007","volume":"13","author":[{"given":"P.","family":"de la Torre","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Greenlaw","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. A.","family":"Sch\u00e4ffer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. P. Brent","year":"1974","unstructured":"R. P. Brent, The parallel evaluation of general arithmetic expressions,Journal of the ACM,21 (1974), 201?206.","journal-title":"Journal of the ACM"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole, Parallel merge sort,SIAM Journal on Computing,17 (1988), 770?785.","journal-title":"SIAM Journal on Computing"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/SPDP.1991.218243"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1142\/S0129626492000155","volume":"2","author":"P. Torre de la","year":"1992","unstructured":"P. de la Torre, R. Greenlaw, and T. M. Przytycka, The optimal tree ranking problem is inNC,Parallel Processing Letters,2 (1992), 31?41.","journal-title":"Parallel Processing Letters"},{"key":"CR5","unstructured":"P. de la Torre, R. Greenlaw, and A. A. Sch\u00e4ffer, Optimal Edge Raking of Trees in Polynomial Time, Technical Report 92-10, University of New Hampshire, 1993."},{"key":"CR6","unstructured":"P. de la Torre, R. Greenlaw, and A. A. Sch\u00e4ffer, A Note on Deogun and Peng's Edge Ranking Algorithm, Technical Report 93-13, University of New Hampshire, 1993."},{"key":"CR7","first-page":"19","volume":"79","author":"J. S. Deogun","year":"1990","unstructured":"J. S. Deogun and Y. Peng, Edge ranking of trees,Congressus Numerantium,79 (1990), 19?28.","journal-title":"Congressus Numerantium"},{"key":"CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","volume":"21","author":"L. M. Goldschlager","year":"1982","unstructured":"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.","journal-title":"Theoretical Computer Science"},{"key":"CR10","volume-title":"Computing Science Series","author":"R. Greenlaw","year":"1995","unstructured":"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."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0020-0190(88)90194-9","volume":"28","author":"A. V. Iyer","year":"1988","unstructured":"A. V. Iyer, H. D. Ratliff, and G. Vijayan, Optimal node ranking of trees,Information Processing Letters,28 (1988), 225?229.","journal-title":"Information Processing Letters"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0166-218X(91)90012-L","volume":"30","author":"A. V. Iyer","year":"1991","unstructured":"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.","journal-title":"Discrete Applied Mathematics"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J. M. Lewis","year":"1980","unstructured":"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.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/SPDP.1990.143502"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms,Journal of the ACM,30 (1983), 852?865.","journal-title":"Journal of the ACM"},{"key":"CR16","volume-title":"Concurrent Design of Products and Processes","year":"1989","unstructured":"J. Nevins and D. Whitney, editors,Concurrent Design of Products and Processes, McGraw-Hill, New York, 1989."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(82)90011-1","volume":"19","author":"Y. Perl","year":"1982","unstructured":"Y. Perl and S. Zaks, On the complexity of edge labelings for trees,Theoretical Computer Science,19 (1982), 1?16.","journal-title":"Theoretical Computer Science"},{"key":"CR18","unstructured":"T. M. Przytycka, The optimal tree ranking problem is inNC Manuscript, 1991."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0020-0190(89)90161-0","volume":"33","author":"A. A. Sch\u00e4ffer","year":"1989\/90","unstructured":"A. A. Sch\u00e4ffer, Optimal node ranking of trees in linear time,Information Processing Letters,33 (1989\/90), 91?96.","journal-title":"Information Processing Letters"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M. Yannakakis","year":"1981","unstructured":"M. Yannakakis, Node-deletion problems on bipartite graphs,SIAM Journal on Computing,10 (1981), 310?327.","journal-title":"SIAM Journal on Computing"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M. Yannakakis","year":"1981","unstructured":"M. Yannakakis, Edge-deletion problems,SIAM Journal on Computing,10 (1981), 297?309.","journal-title":"SIAM Journal on Computing"},{"key":"CR22","first-page":"118","volume-title":"Lecture Notes in Computer Science, Volume 855","author":"X. Zhou","year":"1994","unstructured":"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."},{"key":"CR23","unstructured":"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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01189071.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01189071\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01189071","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T16:41:50Z","timestamp":1556728910000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01189071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["BF01189071"],"URL":"https:\/\/doi.org\/10.1007\/bf01189071","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}