{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:46Z","timestamp":1787323006354,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>A $k$-ranking of a graph $G$ is a labeling of its vertices from $\\{1,\\ldots,k\\}$ such that any nontrivial path whose endpoints have the same label contains a larger label. The least $k$ for which $G$ has a $k$-ranking is the ranking number of $G$, also known as tree-depth. Applications of rankings include VLSI design, parallel computing, and factory scheduling. The on-line ranking problem asks for an algorithm to rank the vertices of $G$ as they are revealed one at a time in the subgraph of $G$ induced by the vertices revealed so far (each previously revealed vertex appears with its label, but the final placement of the induced subgraph in $G$ is not specified). The on-line ranking number of $G$ is the minimum over all such algorithms of the largest label that algorithm can be forced to use. We give algorithmic bounds on the on-line ranking number of trees in terms of maximum degree, diameter, and number of internal vertices.<\/jats:p>","DOI":"10.1137\/130932946","type":"journal-article","created":{"date-parts":[[2015,1,20]],"date-time":"2015-01-20T12:21:39Z","timestamp":1421756499000},"page":"145-156","source":"Crossref","is-referenced-by-count":2,"title":["On-Line Vertex Ranking of Trees"],"prefix":"10.1137","volume":"29","author":[{"given":"Daniel C.","family":"McDonald","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,1,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990587"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1537"},{"key":"atypb3","first-page":"195","volume":"15","author":"Borowiecki P.","year":"2013","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1094"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.11.072"},{"key":"atypb6","first-page":"193","volume":"187","author":"Bunde D. P.","year":"2007","journal-title":"Congr. Numer."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/120880471"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446682"},{"key":"atypb9","first-page":"5","author":"Chen K.","year":"2009","journal-title":"ACM Trans. Algorithms"},{"key":"atypb10","unstructured":"Y. M. Chen and Y. L. Lai,\n                      An improved on-line node ranking algorithm of trees\n                      , in Proceedings of the 23rd Workshop on Combinatorial Mathematics and Computing Theory, 2006, pp. 345-348."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702431840"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1595"},{"key":"atypb13","first-page":"22","author":"Haque E.","year":"2007","journal-title":"Proceedings of International Conference on Information and Communication Technology"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.03.028"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90194-9"},{"key":"atypb16","first-page":"111","volume":"164","author":"Jamison R. E.","year":"2003","journal-title":"Congr. Numer."},{"key":"atypb17","first-page":"46","author":"Juan J. S.","year":"2005","journal-title":"Las Vegas"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J. S. Juan, C. Lee, and T. Wu,\n                      An on-line parallel algorithm for node ranking of trees\n                      , in Algorithms and Architectures for Parallel Processing, Lecture Notes in Comput. Sci. 5574, 2009, Springer, New York, pp. 384-395.","DOI":"10.1007\/978-3-642-03095-6_37"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s10587-006-0040-6"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00215-0"},{"key":"atypb22","unstructured":"Z. Tuza and M. Voigt,\n                      Ranking problems on graphs\n                      , manuscript, 1995."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130932946","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:36:43Z","timestamp":1787319403000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130932946"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130932946"],"URL":"https:\/\/doi.org\/10.1137\/130932946","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}