Efficient splitting off algorithms for graphs
Efficient splitting off algorithms for graphs
复制标题
高效的图分割算法
DOI：
10.1145/195058.195436
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
H. Gabow
中科院分区：
文献类型：
--
作者：
H. Gabow
分开是一个强大的工具，用于证明定理并在图形上开发多项式算法，尤其是对于边缘连接性问题。我们提出有效的算法进行分类，从而导致连通性问题的有效算法。我们改善了vious算法（在子模量上进行BAA），以找到无方向图或多格画的K边缘连接方向。我们还改善了无向和有向多编码的边缘连接增强问题的节拍界限，以及在无向图和多编码上的局部连通性y增强问题中，每个都通过一个因素n。我们还提供了有效的算法，以找到无方向图或多编码的均衡取向。我们的方法是图形转换，可以有效地计算最小s，t-cut的变体的切割。
Splitting off is a powerful tool for proving theorems and developing polynomial-time algorithms on graphs, especially for edge-connectivity problems. We present efficient algorithms for splitting off, leading to efficient algorithms for connectivity problems. We improve pr~ vious algorithms (baaed on submodular flow) to find a k-edge-connected orientation of an undirected graph or Multigraph. We also improve the beat bounds for the edge connectivity augmentation problem for undirected and directed multigraphs, and for the local connectivity y augmentation problem on undirected graphs and multigraphs, each by a factor n. We also give efficient algorithms for finding a well-balanced orientation of an undirected graph or Multigraph. Our approach mea a graph transformation that allows efficient computation of cuts that are variants of the minimum s, t-cut.