The average size of ordered binary subgraphs
Hartel, Pieter H. (1988) The average size of ordered binary subgraphs. In: International Workshop WG '88 , June 15–17, 1988, Amsterdam, The Netherlands (pp. pp. 327351).

PDF
957kB 
Abstract:  To analyse the demands made on the garbage collector in a graph reduction system, the change in size of an average graph is studied when an arbitrary edge is removed. In ordered binary trees the average number of deleted nodes as a result of cutting a single edge is equal to the average size of a subtree. Under the assumption that all trees with n nodes are equally likely to occur, the expected size of a subtree is found to be approximately radicpgrn. The enumeration procedure can be applied to graphs by considering spanning trees in which the nodes that were shared in the graph are marked in the spanning tree. A correction to the calculation of the average is applied by ignoring subgraphs that have a marked root. Under the same assumption as above the average size of a subgraph is approximately radicpgrn2(m+1), where m represents the number of shared nodes and mLtn. 
Item Type:  Conference or Workshop Item 
Copyright:  © 1988 SpringerVerlag 
Link to this item:  http://purl.utwente.nl/publications/55756 
Official URL:  http://dx.doi.org/10.1007/3540507280_55 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page