MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $T$ be a rooted tree with root $r$. Say an ordering $v_1,\ldots,v_n$ of the vertices of $T$ is a search order if $v_1=r$ and for all $2 \leq i \leq n$, there is $j < i$ such that $v_j$ is the parent of $v_i$. In other words, parents are explored before their children in the order.

For a given search order $v_1,\ldots,v_n$, let $w(v_i)=\max(j:v_iv_j \in E(T))-\min(j:v_jv_i \in E(T))$. The max is the time the last child of $v_i$ is explored, and the min is the time the parent of $v_i$ is explored. Say the width of the order is $\max(w(v_i):1 \leq i \leq n)$, and say the width of $T$ is the minimum width of an ordering of $T$.

Is anything known about the width? Is it a known concept under another name? Have any theorems been proved about it? Any equivalent characterizations/definitions? Any useful bounds, perhaps in terms of the maximum degree of $T$?

Edit: This is the directed bandwidth, as David Eppstein points out below. I'm still interested in any bounds -- perhaps some upper bound with a simple form, perhaps even with an approximation guarantee?

share|cite|improve this question
Maybe the width of the order is max(w(v_i))? – JBL Oct 15 '10 at 23:02
Yes, thanks JBL – Louigi Addario-Berry Oct 15 '10 at 23:05
>Any useful bounds, perhaps in terms of the maximum degree of T? Did you mean in term of the degree and and size of the tree? The binary tree of height $h$ has a width that is roughly its size, no? – Ori Gurel-Gurevich Oct 16 '10 at 4:17
Ori, yes, my suggestion was ill-thought-out. I guess breadth-first search always gives an upper-bound that is of the order of the greatest number of nodes in any single generation. This is roughly tight for a complete binary tree but not in general. – Louigi Addario-Berry Oct 16 '10 at 10:45
up vote 4 down vote accepted

What you call width is known more specifically as "directed bandwidth". It's known to be NP-complete even for trees; see Complexity Results for Bandwidth Minimization, M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth, SIAM Journal on Applied Mathematics Vol. 34, No. 3 (May, 1978), pp. 477-495. The hardness of the undirected case for trees (without the parent-child ordering constraint) is detailed in section 8 of the paper, and in section 9 they claim without giving a detailed proof that it's also hard in the directed case.

share|cite|improve this answer
Thanks very much David! – Louigi Addario-Berry Oct 16 '10 at 15:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.