Dynamic Plane Transitive Closure

Krzysztof Diks, Piotr SankowskiESA 2007 · OpenReview

Abstract

In this paper we study the problem of transitive closure in dynamic directed plane graphs. We show a dynamic algorithm supporting updates and queries in worst-case \(\tilde{O}(\sqrt{n})\) time. This is the first known algorithm for this problem with almost linear update time and query time product.
BibTeX
@inproceedings{diks2007dynamic,
  author = {Krzysztof Diks and Piotr Sankowski},
  title = {{Dynamic Plane Transitive Closure}},
  booktitle = {ESA},
  year = {2007},
  url = {https://openreview.net/forum?id=kUcEJjmih8},
}

Loading related content...

Figure