Exécution de notre outil de synthèse sur un nouvel article
Vérifiez l’article ci-dessous, puis lancez sa synthèse.
Algorithms for Dynamic Reeb Graphs
Salman Parsa
arXiv: 1402.2812v3 (cs.CG)
There was a problem with the argument used in the original submission. It seems that the truly dynamic nature of the problem puts it in the category of problems such as dynamic graph connectivity that do not have known poly-logarithmic algorihtms. To see the claims in the abstract and a reduction of the problem to a dynamic graph problem refer to my PhD thesis
Licence : NONEXCLUSIVE-DISTRIB 1.0
Résumé : We present an algorithm for updating the Reeb graph under fully dynamic changes of the function values. The basic event is the interchange of two consecutive vertex values. The algorithm updates the Reeb graph in $O(l g{n})$ worst-case deterministic time for each such interchange, where $l$ is an upper bound on the size of the star of the involved vertices, and g(n) is a worst-case bound for the dynamic graph connectivity problem. Moreover, we argue that $O(l)$ is a lower bound for this operation in general.
Soumis à arXiv le 12 Fév. 2014