论文标题
优化平均体重的边缘切割：福特和富克森的新替代品
Edge-cuts Optimized for Average Weight: a new alternative to Ford and Fulkerson
论文作者
论文摘要
令$ g $为与权重$ w：e（g）\ rightarrow r^+$相关的有向图。对于$ g $的边缘切口$ q $，$ q $的平均权重表示并定义为$ w_ {ave}（q）= \ frac {\ sum_ {e \ in q} w（e）} {| q | |} $。最佳平均重量的边缘切割是一个边缘切割$ Q $，因此在所有边缘切割中（或最小值，对称地）中，$ W_ {AVE}（Q）$是最大的。在本文中，证明了此问题的多项式算法用于在根部树上找到这样的最佳边缘切割，将所有叶子的根和集合分开。该算法使我们能够开发一种自动聚类方法，并更准确地检测嵌入层次树结构中的社区。
Let $G$ be a directed graph associated with a weight $w: E(G) \rightarrow R^+$. For an edge-cut $Q$ of $G$, the average weight of $Q$ is denoted and defined as $w_{ave}(Q)=\frac{\sum_{e\in Q}w(e)}{|Q|}$. An edge-cut of optimal average weight is an edge-cut $Q$ such that $w_{ave}(Q)$ is maximum among all edge-cuts (or minimum, symmetrically). In this paper, a polynomial algorithm for this problem is proved for finding such an optimal edge-cut in a rooted tree, separating the root and the set of all leafs. This algorithm enables us to develop an automatic clustering method with more accurate detection of communities embedded in a hierarchy tree structure.
