Loading...
Please wait, while we are loading the content...
Similar Documents
When bad things happen to good trees
| Content Provider | CiteSeerX |
|---|---|
| Author | Aivaliotis, Manuel Gordon, Gary Graveman, William |
| Abstract | When the edges in a tree or rooted tree failwith a certain fixed probability, the (greedoid) rank may drop. We compute the expected rank as a polynomial in p and as a realnumber under the assumption of uniform distribution. We obtain severaldifferent expressions for this expected rank polynomial for both trees and rooted trees, one of which is especially simple in each case. We also prove two extremal theorems that determine both the largest and smallest values for the expected rank of a (rooted or unrooted) tree, and precisely when these extreme bounds are achieved. We conclude with directions for further study. |
| File Format | |
| Volume Number | 37 |
| Journal | J. GRAPH THEORY |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Bad Thing Good Tree Expected Rank Severaldifferent Expression Tree Failwith Expected Rank Polynomial Uniform Distribution Certain Fixed Probability Extreme Bound Extremal Theorem |
| Content Type | Text |
| Resource Type | Article |
