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?

  • $\begingroup$ Maybe the width of the order is max(w(v_i))? $\endgroup$ – JBL Oct 15 '10 at 23:02
  • $\begingroup$ >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? $\endgroup$ – Ori Gurel-Gurevich Oct 16 '10 at 4:17
  • $\begingroup$ 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. $\endgroup$ – Louigi Addario-Berry Oct 16 '10 at 10:45

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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