2001 | OriginalPaper | Buchkapitel
On the Validity of Hierarchical Decompositions
verfasst von : Irene Finocchi, Rossella Petreschi
Erschienen in: Computing and Combinatorics
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Hierarchical decompositions are a useful tool for drawing large graphs. Such decompositions can be represented by means of a data structure called hierarchy tree. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given property P: this notion reflects the similarity between the topological structure of the original graph and of any high-level representation of it obtained from the hierarchy tree. We study the P-validity when the clustered graph is a tree and property P is the acyclicity, presenting a structure theorem for the P-validity of hierarchy trees under these hypotheses.