Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Constant Time Generation of Trees with Specified Diameter
verfasst von : Shin-ichi Nakano, Takeaki Uno
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
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
Many algorithms to generate all trees with
n
vertices without repetition are already known. The best algorithm runs in time proportional to the number of trees. However, the time needed to generate each tree may not be bounded by a constant, even though it is “on average”. In this paper we give a simple algorithm to generate all trees with exactly
n
vertices and diameter
d
, without repetition. Our algorithm generates each tree in constant time. It also generates all trees so that each tree can be obtained from the preceding tree by at most three operations. Each operation consists of a deletion of a vertex and an addition of a vertex. By using the algorithm for each diameter 2,3, ⋯ ,
n
− 1, we can generate all trees with
n
vertices.