Dynamic Plane Transitive Closure
Lists
Only you see this
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...