The Minset-Poset Approach to Representations of Graph Connectivity
The Minset-Poset Approach to Representations of Graph Connectivity
复制标题
图连通性表示的最小集-偏集方法
DOI：
10.1145/2764909
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
H. Gabow
中科院分区：
文献类型：
--
作者：
H. Gabow
在文献中，已经提出了最小值的poset（简称为简短）的各种实例，例如，PICARD和QUEYRANNE的代表是所有ST-Mimim cut to flow Network的剪辑。结构很常见。为了有效地找到poset的节点，当F是未加权图的最小边缘剪辑的家族；我们现在描述的是组合的组合和算法。在所有mincuts中。我们的密集图。任何加权挖掘者的最小poset;用于构造该poset的节点的任何未加权的digraph。加权和未加权的图形，我们达到了前两个边界的时间，即基本上是为了计算边缘连接本身的最佳范围。提供是略微的变体，这导致算法在RAM上构造时间O（M）。最近提出了。）
Various instances of the minimal-set poset (minset-poset for short) have been proposed in the literature, e.g., the representation of Picard and Queyranne for all st-minimum cuts of a flow network. We begin with an explanation of why this poset structure is common. We show any family of sets F that can be defined by a “labelling algorithm” (e.g., the Ford-Fulkerson labelling algorithm for maximum network flow) has an algorithm that constructs the minset poset for F. We implement this algorithm to efficiently find the nodes of the poset when F is the family of minimum edge cuts of an unweighted graph; we also give related algorithms to construct the entire poset for weighted graphs. The rest of the article discusses applications to edge- and vertex connectivity, both combinatorial and algorithmic, that we now describe. For digraphs, a natural interpretation of the minset poset represents all minimum edge cuts. In the special case of undirected graphs, the minset poset is proved to be a variant of the well-known cactus representation of all mincuts. We use the poset algorithms to construct the cactus representation for unweighted graphs in time O(m+λ2 n log (n/λ)) (λ is the edge connectivity) improving the previous bound O(λ n2) for all but the densest graphs. We also construct the cactus representation for weighted graphs in time O(nm log(n2/m)), the same bound as a previously known algorithm but in linear space O(m). The latter bound also holds for constructing the minset poset for any weighted digraph; the former bound also holds for constructing the nodes of that poset for any unweighted digraph. The poset is used in algorithms to increase the edge connectivity of a graph by adding the fewest edges possible. For directed and undirected graphs, weighted and unweighted, we achieve the time of the preceding two bounds, i.e., essentially the best-known bounds to compute the edge connectivity itself. Some constructions of minset posets for graph rigidity are also sketched. For vertex connectivity, the minset poset is proved to be a slight variant of the dominator tree. This leads to an algorithm to construct the dominator tree in time O(m) on a RAM. (The algorithm is included in the appendix, since other linear-time algorithms of similar simplicity have recently been presented.)