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. 327-351).

open access
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 radicpgrn-2(m+1), where m represents the number of shared nodes and mLtn.
Item Type:Conference or Workshop Item
Copyright:© 1988 Springer-Verlag
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page