Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
Prefix graphs and their applications
verfasst von : Shiva Chaudhuri, Torben Hagerup
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
The range product problem is, for a given set S equipped with an associative operator o, to preprocess a sequence a1,⋯, an of elements from S so as to enable efficient subsequent processing of queries of the form: Given a pair (s, t) of integers with 1≤s≤t≤n, return a s oas+1 o⋯o a t . The generic range product problem and special cases thereof, usually with o computing the maximum of its arguments according to some linear order on S, have been extensively studied. We show that a large number of previous sequential and parallel algorithms for these problems can be unified and simplified by means of prefix graphs.