论文标题
用于计算双人双重发音点和相关问题的线性时间算法
Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems
论文作者
论文摘要
有向图的$ g =（v，e）$如果包含强烈连接的跨度子图，没有任何一对的反平行（或双胞胎）边缘，则可以双重连接。有向图$ g $的双重连接的组件（TSCC）是其最大的双重连接的子图。这些概念具有多种不同的应用，例如电信网络的设计和建筑物的结构稳定性。如果删除$ v $会增加$ g $的TSCC数量，则V $中的顶点$ v \是$ g $的双重强明显点。在这里，我们介绍了第一个线性时间算法，该算法找到了有向图的所有双重强调点。我们表明，在无方向的图中，双双强铰接点的计算减少到以下问题，这可能具有独立的兴趣：给定$ 2 $ - vertex连接（双连接）的无向图$ h $，找到所有属于Vertex-Edge cut-pair的顶点$ v $，即$ e $。 \ {v，e \} $未连接。我们开发了一种线性时间算法，该算法不仅可以找到所有此类顶点$ v $，而且还计算了边缘$ e $的数量，因此未连接$ h \ setMinus \ {v，e \} $。这也意味着，对于每个双胞胎强的发音点$ v $，这不是连接较强的Digraph $ g $中的强烈表达点，我们可以在$ g \ setMinus v $中计算TSCC的数量。我们注意到，可以通过利用$ 3 $ vertex连接的$ 3 $ vertex（三连电）组件的结构来解决属于顶点边缘切割对的所有顶点的问题，该结构由$ h $的SPQR树代表$ h $。但是，我们的方法在概念上很简单，因此可能更适合实际实施。
A directed graph $G=(V,E)$ is twinless strongly connected if it contains a strongly connected spanning subgraph without any pair of antiparallel (or twin) edges. The twinless strongly connected components (TSCCs) of a directed graph $G$ are its maximal twinless strongly connected subgraphs. These concepts have several diverse applications, such as the design of telecommunication networks and the structural stability of buildings. A vertex $v \in V$ is a twinless strong articulation point of $G$ if the deletion of $v$ increases the number of TSCCs of $G$. Here, we present the first linear-time algorithm that finds all the twinless strong articulation points of a directed graph. We show that the computation of twinless strong articulation points reduces to the following problem in undirected graphs, which may be of independent interest: Given a $2$-vertex-connected (biconnected) undirected graph $H$, find all vertices $v$ that belong to a vertex-edge cut-pair, i.e., for which there exists an edge $e$ such that $H \setminus \{v,e\}$ is not connected. We develop a linear-time algorithm that not only finds all such vertices $v$, but also computes the number of edges $e$ such that $H \setminus \{v,e\}$ is not connected. This also implies that for each twinless strong articulation point $v$ which is not a strong articulation point in a strongly connected digraph $G$, we can compute the number of TSCCs in $G \setminus v$. We note that the problem of computing all vertices that belong to a vertex-edge cut-pair can be solved in linear-time by exploiting the structure of $3$-vertex-connected (triconnected) components of $H$, represented by an SPQR tree of $H$. Our approach, however, is conceptually simple, and thus likely to be more amenable to practical implementations.
