On the width of an orientation of a tree

✍ Scribed by M. D. Atkinson; D. T. H. Ng

• Publisher: Springer Netherlands
• Year: 1988
• Tongue: English
• Weight: 641 KB
• Volume: 5
• Category: Article
• ISSN: 0167-8094
• DOI: 10.1007/bf00143896

✦ Synopsis

There are 2"-t ways in which a tree on n vertices can be oriented. Each of these can be regarded as the (Hasse) diagram of a partially ordered set. The maximal and minimal widths of these posets are determined. The maximal width depends on the bipartition of the tree as a bipartite graph and it can be determined in time O(n). The minimal width is one of LA/21 or IA/21 + 1, where 1 is the number of leaves of the tree. An algorithm of execution time O(n +A* log A) to construct the minimal width orientation is given.