On-line vertex ranking of trees

DOI10.1137/130932946MaRDI QIDQ3453569zbMATH OpenOpenAlexFDO

Authors Daniel C. McDonald

Publication date 27 November 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.2669

zbMATH Keywords

on-line rankingrank numbertree-depthtreesvertex ranking

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: 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 presented one at a time along with all previously ranked vertices and the edges between them (so each vertex is presented as the lone unranked vertex in a partially labeled induced subgraph of $G$ whose final placement 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 bounds on the on-line ranking number of trees in terms of maximum degree, diameter, and number of interior vertices.

Recommendations

• List rankings and on-line list rankings of graphs
• On-line rankings of graphs
• On-line ranking of split graphs
• A note on on-line ranking number of graphs
• A lower bound for on-line ranking number of a path

Cited in

(7)

• On-line rankings of graphs
• List rankings and on-line list rankings of graphs
• Ranking intervals under visibility constraints^∗
• On node ranking of complete r-partite graphs
• On-line ranking of split graphs
• The complexity of bicriteria tree-depth
• Competitive Online Search Trees on Trees

This page was built for publication: On-line vertex ranking of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453569)