A fast edge-splitting algorithm in edge-weighted graphs
A fast edge-splitting algorithm in edge-weighted graphs
复制标题
DOI：
10.1093/ietfec/e89-a.5.1263
复制
发表时间：
2006-05-01
影响因子：
0.5
通讯作者：
Nagamochi, Hiroshi
中科院分区：
文献类型：
--
作者：
Nagamochi, Hiroshi
设H是一个具有指定顶点s的图，其边用非负实数加权。分割边e = {u， s}和e‘ = {s， v} at s是一种将e和e’的权值分别减少一个实增量>0 00，同时将边{u， v}的权值增加增量的操作。已知所有与s相关的边都可以在保持H的边连通性的情况下被分离，并且这种完全分裂被用于解决许多连通性问题。本文给出了一个耗时O（mn + n(2) log n）的算法，用于求n顶点m条边图的完全分裂。
Let H be a graph with a designated vertex s, where edges are weighted by nonnegative reals. Splitting edges e = {u, s} and e' = {s, v} at s is an operation that reduces the weight of each of e and e' by a real delta > 0 while increasing the weight of edge {u, v} by delta. It is known that all edges incident to s can be split off while preserving the edge-connectivity of H and that such a complete splitting is used to solve many connectivity problems. In this paper, we give an O(mn + n(2) log n) time algorithm for finding a complete splitting in a graph with n vertices and m edges.