Show simple item record

dc.contributor.authorKarloff, Howarden_US
dc.contributor.authorShirley, Kenneth E.en_US
dc.contributor.editorB. Preim, P. Rheingans, and H. Theiselen_US
dc.date.accessioned2015-02-28T15:30:24Z
dc.date.available2015-02-28T15:30:24Z
dc.date.issued2013en_US
dc.identifier.issn1467-8659en_US
dc.identifier.urihttp://dx.doi.org/10.1111/cgf.12094en_US
dc.description.abstractGiven a very large, node-weighted, rooted tree on, say, n nodes, if one has only enough space to display a knode summary of the tree, what is the most informative way to draw the tree? We define a type of weighted tree that we call a summary tree of the original tree that results from aggregating nodes of the original tree subject to certain constraints. We suggest that the best choice of which summary tree to use (among those with a fixed number of nodes) is the one that maximizes the information-theoretic entropy of a natural probability distribution associated with the summary tree, and we provide a (pseudopolynomial-time) dynamic-programming algorithm to compute this maximum entropy summary tree, when the weights are integral. The result is an automated way to summarize large trees and retain as much information about them as possible, while using (and displaying) only a fraction of the original node set. We illustrate the computation and use of maximum entropy summary trees on five real data sets whose weighted tree representations vary widely in structure. We also provide an additive approximation algorithm and a greedy heuristic that are faster than the optimal algorithm, and generalize to trees with real-valued weights.en_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltd.en_US
dc.subjectI.2.8 [Problem Solvingen_US
dc.subjectControl Methodsen_US
dc.subjectSearch]en_US
dc.subjectDynamic Programmingen_US
dc.subjectG.2.2 [Graph Theory]en_US
dc.subjectTreesen_US
dc.subjectI.4.10 [Image Representation]en_US
dc.subjectHierarchicalen_US
dc.subjectG.2.1 [Combinatorics]en_US
dc.subjectCombinatorial Algorithmsen_US
dc.titleMaximum Entropy Summary Treesen_US
dc.description.seriesinformationComputer Graphics Forumen_US


Files in this item

Thumbnail
Thumbnail
Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record