Dou*_*ean 9 algorithm complexity-theory graph-theory
我知道平面度测试可以在O(v)中进行(等效O(e),因为平面图具有O(v)边)时间.
我想知道它是否可以在O(1)摊销时间在线完成,因为每个边缘被添加(仍然是整个O(e)时间).
换句话说,在表示图形边缘的数据库表中,并且受约束表示所表示的图形是平面的,负责管理约束的DBMS需要多长时间才能验证每个建议的插入？(为简化起见,假设没有删除.)必须重新运行其中一个O(v)平面度测试算法来测试每个建议的插入或插入组吗？
经过一些研究后,似乎答案是"是",有在线算法,但"否"没有O(1)摊销的运行时间.
这是1999年ACM期刊论文,应用程序的全动态平面度测试,作者写道:
特别地,我们在平面图G上考虑以下三个操作:(i)如果结果图保持平面,则插入边; (ii)删除边缘; (iii)测试是否可以在不违反平面性的情况下将边缘添加到图形中.我们展示了如何在O(n ^ 2/3)时间内支持上述每个操作,其中n是图中顶点的数量.测试和删除的界限是最坏情况,而插入的界限是摊销的.
我还发现了1989年论文的摘要,增量平面度测试声称边缘插入的O(log n)边界,但我不确定他们的技术是否也包括删除.
在1999年的一篇论文" 快速增量平面度测试"中讨论过,1999年的论文也提到了一个O(逆ackermann(total-operations,n))算法用于无删除的情况,但CiteSeer目前正在下降,所以我'稍后会阅读详细信息.
删除对我的应用程序很有用,并且可以访问J. ACM论文,我将进一步阅读有关摊销的O(n ^ 2/3)策略.