Aarhus University Seal

Path Minima Queries in Dynamic Weighted Trees

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Department of Computer Science
In the path minima problem on a tree, each 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, where the edge weights can be updated, we give data structures that achieve optimal query time\todo{what about update time?} in the comparison and the RAM models. These structures also support inserting a node on an edge, inserting a leaf, and contracting edges. When only insertion and deletion of leaves are desired, we give data structures in the comparison and the RAM models, with optimal query time that is significantly lower than when updating the weights is allowed. We also consider the problem in the semigroup model, and show lower bounds for different variants of the problem.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)290-301
Number of pages12
Publication statusPublished - 2011
Event11th International Symposium on Algorithms and Data Structures. WADS 2011 - New York, NY, United States
Duration: 15 Aug 201117 Aug 2011


Conference11th International Symposium on Algorithms and Data Structures. WADS 2011
CountryUnited States
CityNew York, NY

Bibliographical note

Title of the vol.: Algorithms and Data Structures / Frank Dehne, John Iacono and Jörg-Rüdiger Sack (eds.)
ISBN: 978-3-642-22299-3

See relations at Aarhus University Citationformats

ID: 41505353