✦ LIBER ✦

Optimal Labellings of Rooted Directed Trees

✍ Scribed by Jia-yu Shao

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 200 KB
Volume: 21
Category: Article
ISSN: 0196-8858
DOI: 10.1006/aama.1998.0579

No coin nor oath required. For personal study only.

✦ Synopsis

We consider an optimal labelling problem for a rooted directed tree abbreviated . as ''RDT'' which is motivated by certain scheduling problem. We obtain several necessary and sufficient conditions for the optimal labellings of a RDT and give a polynomially bounded algorithm for constructing the optimal labellings of a RDT. We also generalize the problem and the corresponding results to the case of vertex weighted RDTs.

📜 SIMILAR VOLUMES

Parallel Shortcutting of Rooted Trees

✍ Mikkel Thorup 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 305 KB

First it is shown that for any rooted tree T with n vertices, and parameter m G n, there is a ''shortcutting'' set S of at most m arcs from the transitive closure Ž . T\* of T such for any ¨, w g T \*, there is a dipath in T j S from ¨to w of length Ž Ž .. Ž O ␣ m, n . An equivalent result has been

Complexes of Directed Trees

✍ Dmitry N. Kozlov 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 153 KB

To every directed graph G one can associate a complex 2(G) consisting of directed subforests. This construction, suggested to us by R. Stanley, is especially important in the case of a complete double directed graph G n , where it leads to the study of some interesting representations of the symmetr

On the Total Heights of Random Rooted Bi

On the Total Heights of Random Rooted Binary Trees

✍ L. Takacs 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 306 KB

Denote by \(S_{n}\) the set of all distinct rooted binary trees with \(n\) unlabeled vertices. Define \(\sigma_{n}\) as a total height of a tree chosen at random in the set \(S_{n}\), assuming that all the possible choices are equally probable. The total height of a tree is defined as the sum of the

Optimal tree 3-spanners in directed path

Optimal tree 3-spanners in directed path graphs

✍ Le, Ho�ng-Oanh; Le, Van Bang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB 👁 2 views

In a graph G, a spanning tree T is called a tree t-spanner of G if the distance between any two vertices in T is at most t times their distance in G. While the complexity of finding a tree t-spanner of a given graph is known for any fixed t 3, the case t ϭ 3 still remains open. In this article, we s

Direct measurement of groundwater uptake

Direct measurement of groundwater uptake through tree roots in a cave

✍ Tanya M. Doody; Richard G. Benyon 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 170 KB

## Abstract Recent intensive research investigating groundwater extraction of __Pinus radiata__ D. Don plantations in south east South Australia has focused on measurement of sapflow rates in __P. radiata__ stems above ground. An extended dry period in summer 2001 provided an opportunity to install

Convex labelings of trees

✍ Stephen J. Dow; Douglas F. Rall; Peter J. Slater 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 456 KB

A convex labeling of a tree T o f order n is a one-to-one function f from the vertex set of Tinto the nonnegative integers, so that f ( y ) 5 ( f ( x ) t f(z))/2 for every path x, y, z of length 2 in T. If, in addition, f (v) I n -1 for every vertex v of T, then f is a perfect convex labeling and T