# Edge-cuts Optimized for Average Weight: a new alternative to Ford and Fulkerson

arXiv: https://arxiv.org/abs/2002.00263 · HTML: https://mlsanity.com/paper/2002.00263/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2020.

## Built on by (most cited first, 1 of 1)

- [The Automatic Quasi-clique Merger algorithm (AQCM)](https://mlsanity.com/paper/2103.04186/) (2021)

## Abstract (arXiv)

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 wave(Q)=fracsume∈ Qw(e)|Q|. An edge-cut of optimal average weight is an edge-cut Q such that wave(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.