Fully Dynamic Recognition of Proper Circular-Arc Graphs
Fully Dynamic Recognition of Proper Circular-Arc Graphs
复制标题
真圆弧图的全动态识别
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
1.1
通讯作者：
Francisco J. Soulignac
中科院分区：
文献类型：
--
作者：
Francisco J. Soulignac
我们提出了一个完全动态的算法识别适当的圆弧（PCA）图。图上允许的操作包括插入和删除顶点（连同其关联边）或边。边操作花费O（logn）时间，其中n是图的顶点数，而顶点操作花费O（logn+d）时间，其中d是修改顶点的度。我们还展示了每个插入或删除边的增量和减量算法，其时间复杂度为O（1）。作为我们的算法的一部分，完全动态的连接和协同连接算法，工作在O（logn）时间每操作。此外，提供了用于确定PCA表示是否对应于共二分图的O（Δ）时间算法，其中Δ是顶点的度中的最大值。当图是共二分图时，在相同的时间内获得其每个共分量的共二分图。作为一个应用，我们展示了如何在O（n+m）时间内找到静态图的最小禁止导出子图。
We present a fully dynamic algorithm for the recognition of proper circular-arc (PCA) graphs. The allowed operations on the graph involve the insertion and removal of vertices (together with its incident edges) or edges. Edge operations cost O(logn) time, where n is the number of vertices of the graph, while vertex operations cost O(logn+d) time, where d is the degree of the modified vertex. We also show incremental and decremental algorithms that work in O(1) time per inserted or removed edge. As part of our algorithm, fully dynamic connectivity and co-connectivity algorithms that work in O(logn) time per operation are obtained. Also, an O(Δ) time algorithm for determining if a PCA representation corresponds to a co-bipartite graph is provided, where Δ is the maximum among the degrees of the vertices. When the graph is co-bipartite, a co-bipartition of each of its co-components is obtained within the same amount of time. As an application, we show how to find a minimal forbidden induced subgraph of a static graph in O(n+m) time.