𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Pessimistic Search and the Straightening Involution for Trees

✍ Scribed by William Y.C. Chen

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
106 KB
Volume
19
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

We introduce the idea of pessimistic search on a rooted tree, and develop the straightening involution to relate the inversion polynomial evaluated at q = -1 to the number of even rooted trees. We obtain a differential equation for the inversion polynomial of cyclic trees evaluated at q = -1, a problem proposed by Gessel, Sagan and Yeh. Some brief discussions about relevant topics are also presented.

πŸ“œ SIMILAR VOLUMES

On the complexity of branch-and-bound se
On the complexity of branch-and-bound search for random trees
✍ Luc Devroye; Carlos Zamora-Cura πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 256 KB πŸ‘ 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co

A tabu search heuristic for the Steiner
A tabu search heuristic for the Steiner Tree Problem
✍ Gendreau, Michel; Larochelle, Jean-Francois; SansοΏ½, Brunilde πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 342 KB πŸ‘ 2 views

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as ATM, since it appears as the inherent mathematical structure behind multicast communications. In this paper, we present a tabu se

The virtue and vice of workplace conflic
The virtue and vice of workplace conflict: food for (pessimistic) thought
✍ Carsten K.W. De Dreu πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 140 KB

## Abstract Many authors, myself included, have suggested that workplace conflict may be beneficial to the organization. I argue that the support for this conclusion is rather weak. A selective and necessarily limited review of the literature shows that: (1) the positive functions of conflict are f

A tabu search algorithm for the Capacita
A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
✍ Sharaiha, Yazid M.; Gendreau, Michel; Laporte, Gilbert; Osman, Ibrahim H. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 150 KB πŸ‘ 2 views

The Capacitated Shortest Spanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the weight of every subtree linked to the root by an edge does not exceed a prescribed capacity. We propose a tabu search heuristic for this problem, as well as dynami