The average size of ordered binary subgraphs

J. van Leeuwen (Editor), Pieter H. Hartel

    Research output: Contribution to conferencePaperAcademicpeer-review

    62 Downloads (Pure)

    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 $\sqrt{\pi n}$. 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 $\sqrt{\pi n}-2(m+1)$, where $m$ represents the number of shared nodes and $m \ll n$.
    Original languageUndefined
    Pages327-351
    Number of pages25
    DOIs
    Publication statusPublished - Jun 1988
    Event14th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1988 - Amsterdam, Netherlands
    Duration: 15 Jun 198817 Jun 1988
    Conference number: 14

    Conference

    Conference14th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1988
    Abbreviated titleWG
    CountryNetherlands
    CityAmsterdam
    Period15/06/8817/06/88

    Keywords

    • IR-55756
    • EWI-1248

    Cite this