Path Minima Queries in Dynamic Weighted Trees

Gerth Stølting Brodal, Pooya Davoodi, and S. Srinivasa Rao

In Proc. 12th International Workshop on Algorithms and Data Structures, volume 6844 of Lecture Notes in Computer Science, pages 290-301. Springer Verlag, Berlin, 2011.

Abstract

In the path minima problem on trees each tree edge is assigned a weight and a query asks for the edge with minimum weight on a path between two nodes. For the dynamic version of the problem on a tree, where the edge-weights can be updated, we give comparison-based and RAM data structures that achieve optimal query time. These structures support inserting a node on an edge, inserting a leaf, and contracting edges. When only insertion and deletion of leaves in a tree are needed, we give two data structures that achieve optimal and significantly lower query times than when updating the edge-weights is allowed. One is a semigroup structure for which the edge-weights are from an arbitrary semigroup and queries ask for the semigroup-sum of the edge-weights on a given path. For the other structure the edge-weights are given in the word RAM. We complement these upper bounds with lower bounds for different variants of the problem.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2011. All rights reserved.

Online version

wads11.pdf (284 Kb)

DOI

10.1007/978-3-642-22300-6_25

Links

BIBTEX entry

@incollection{wads11,
  author = "Gerth St{\o}lting Brodal and Pooya Davoodi and S. Srinivasa Rao",
  booktitle = "Proc. 12th International Workshop on Algorithms and Data Structures",
  doi = "10.1007/978-3-642-22300-6_25",
  isbn = "978-3-642-22299-3",
  pages = "290-301",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Path Minima Queries in Dynamic Weighted Trees",
  volume = "6844",
  year = "2011"
}