Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
Labelled trees and pairs of input-output permutations in priority queues
verfasst von : M. Golin, S. Zaks
Erschienen in: Graph-Theoretic Concepts in Computer Science
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
A priority queue can transform a permutation π of a set of size n to some but not necessarily all permutations σ. A recent result of Atkinson and Thiyagarajah [1] states that the number of distinct pairs (π, σ) is (n+1)n−1. Recall that Cayley's Theorem ([2]) states that the number of labelled trees on n+1 nodes is also equal to (n+1)n−1. We present a direct correspondence between these labelled trees and these pairs of permutations and discuss related problems.