论文标题
强烈弦图的半动态算法
Semi-dynamic Algorithms for Strongly Chordal Graphs
论文作者
论文摘要
关于大量图理论问题的动态算法有广泛的文献，特别是对于所有最短路径问题的各种。本文的依赖是一种完全动态的算法，这些算法以弦图已知。但是，据我们所知，对于强烈的和弦图的动态算法问题，没有进行任何研究。为了解决这一差距，在本文中，我们提出了一种半动态算法，用于边缘消失，并提出了一种在强烈的和弦图中的边缘插入的半动态算法，$ g =（v，e）$，$ n $ Vertices和$ m $ edges。边缘删除的查询复杂性为$ O（d_u^2d_v^2（n + m））$，其中$ d_u $和$ d_v $是顶点$ u $和$ v $的候选$ \ \ \ {u，v \} $的$ v $的学位，而Query-complexity的ed gery-complexity of ende-edend exde-enge-insertion $ o（n^2）
There is an extensive literature on dynamic algorithms for a large number of graph theoretic problems, particularly for all varieties of shortest path problems. Germane to this paper are a number fully dynamic algorithms that are known for chordal graphs. However, to the best of our knowledge no study has been done for the problem of dynamic algorithms for strongly chordal graphs. To address this gap, in this paper, we propose a semi-dynamic algorithm for edge-deletions and a semi-dynamic algorithm for edge-insertions in a strongly chordal graph, $G = (V, E)$, on $n$ vertices and $m$ edges. The query complexity of an edge-deletion is $O(d_u^2d_v^2 (n + m))$, where $d_u$ and $d_v$ are the degrees of the vertices $u$ and $v$ of the candidate edge $\{u, v\}$, while the query-complexity of an edge-insertion is $O(n^2)$.
