Searching in dynamic tree-like partial orders

DOI10.1007/978-3-642-22300-6_43MaRDI QIDQ5199269zbMATH OpenOpenAlexFDO

Authors Brent Heeringa, Marius Cătălin Iordan, Louis Theran

Publication date 12 August 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.1316

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We give the first data structure for the problem of maintaining a dynamic set of n elements drawn from a partially ordered universe described by a tree. We define the Line-Leaf Tree, a linear-sized data structure that supports the operations: insert; delete; test membership; and predecessor. The performance of our data structure is within an O(log w)-factor of optimal. Here w <= n is the width of the partial-order---a natural obstacle in searching a partial order.

Recommendations

• Priority Search Trees
• Dynamic ordered sets with exponential search trees
• Searching ordered structures
• An efficient implicit data structure for relation testing and searching in partially ordered sets
• Dynamic LCA Queries on Trees

Cited in

(7)

• Dynamic ordered sets with exponential search trees
• Searching in Trees, Series-Parallel and Interval Orders
• Search in an Ordered Array Having Variable Probe Cost
• scientific article; zbMATH DE number 2101003 (Why is no real title available?)
• Linearizing partial search orders
• Competitive Online Search Trees on Trees
• An optimal algorithm for sorting in trees

This page was built for publication: Searching in dynamic tree-like partial orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199269)