A strongly connected graph is strongly biconnected if after ignoring the direction of its edges we have an undirected graph with no articulation points. A 3-vertex strongly biconnected graph is a strongly biconnected digraph that has the property that deleting any two vertices in this graph leaves a strongly binconnected subgraph. Jaberi [11] presented approximation algorithms for minimum cardinality 2-vertex strongly biconnected directed subgraph problem. We will focus in this paper on polynomial time algorithms which we have implemented for producing spanning subgraphs that are 3-vertex strongly biconnected.
翻译：如果在忽略其边缘方向之后,我们有一个没有连接点的未定向图,则一个强烈连接的图表具有强烈的双连接图。一个3个顶端强烈的双连接图是一个强烈的双连接图,其属性是删除本图中的任何两个顶点,留下一个强烈连接的子图。Jaberi [11] 提出了最小基点2-顶点强烈连接的双连接引导子图问题的近似算法。我们将在本文中重点介绍我们为生成3个顶点紧密连接的横贯子图而实施的多指针时间算法。
相关内容
微信扫码咨询专知VIP会员