# Gomory Hu Tree and Pendant Pairs of a Symmetric Submodular System

Saeid Hanifehnezhad, Ardeshir Dolati

► To cite this version:

Saeid Hanifehnezhad, Ardeshir Dolati. Gomory Hu Tree and Pendant Pairs of a Symmetric Submodular System. 2nd International Conference on Topics in Theoretical Computer Science (TTCS), Sep 2017, Tehran, Iran. pp.26-33, 10.1007/978-3-319-68953-1_3 . hal-01760643

HAL Id: hal-01760643

https://inria.hal.science/hal-01760643

Submitted on 6 Apr 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Gomory Hu Tree and Pendant Pairs of a Symmetric Submodular System

Saeid Hanifehnezhad and Ardeshir Dolati*

Department of Mathematics, Shahed University

Tehran, Iran

`{s.hanifehnezhad,dolati}@shahed.ac.ir`

**Abstract.** Let $S = (V, f)$, be a symmetric submodular system. For two distinct elements $s$ and $l$ of $V$, let $\Gamma(s, l)$ denote the set of all subsets of $V$ which separate $s$ from $l$. By using every Gomory Hu tree of $S$ we can obtain an element of $\Gamma(s, l)$ which has minimum value among all the elements of $\Gamma(s, l)$. This tree can be constructed iteratively by solving $|V| - 1$ minimum $sl$-separator problem. An ordered pair $(s, l)$ is called a pendant pair of $S$ if $\{l\}$ is a minimum $sl$-separator. Pendant pairs of a symmetric submodular system play a key role in finding a minimizer of this system. In this paper, we obtain a Gomory Hu tree of a contraction of $S$ with respect to some subsets of $V$ only by using contraction in Gomory Hu tree of $S$. Furthermore, we obtain some pendant pairs of $S$ and its contractions by using a Gomory Hu tree of $S$.

**Keywords:** Symmetric submodular system, Contraction of a system, Pendant pair, Maximum adjacency ordering, Gomory-Hu tree.

## 1 Introduction

Let $V$ be a finite set. A set function $f: 2^V \to \mathbb{R}$ is called a submodular function if and only if for all $X, Y \in 2^V$, we have

$$f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y). \qquad (1)$$

Submodular functions play a key role in combinatorial optimization, see [3] for further discussion. Rank functions of matroids, cut capacity functions and entropy functions are some well known examples of submodular functions. For a given system $S = (V, f)$, let $f: 2^V \to \mathbb{R}$ be a submodular function. The problem in which we want to find a subset $X \subseteq V$, for which $f(X) \leq f(Y)$ for all $Y \subseteq V$ is called submodular system minimization problem. Minimizing a submodular system is one of the most important problems in combinatorial optimization. Many problems in combinatorial optimization, such as finding minimum cut and minimum $st$-cut in graphs, or finding the largest common independent set in two matroids can be modeled as a submodular function minimization. Image segmentation [1, 8, 9], speech analysis [11, 12], wireless and power networks

<footnote>* Corresponding author. Email: dolati@shahed.ac.ir</footnote>
[20] are only a small part of applications of minimizing submodular functions. Grotchel, Lovasz and Scherijver have developed the first weakly and strongly polynomial time algorithm for minimizing submodular systems in [6] and [13], respectively. Each of them is designed based on the ellipsoid method. Then, nearly simultaneously Scherijver [18] and Iwata, Fleischer, and Fujishige [7] gave a combinatorial strongly polynomial time algorithms for this problem. Later, a faster algorithm for minimizing submodular system was proposed by Orlin [16]. To the best of our knowledge, the fastest algorithm to find a minimizer of a submodular system $\mathcal{S} = (V, f)$ is due to Lee et al [10]. Their algorithm runs in $O(|V|^3 \log^2|V|\tau + |V|^4 \log^{O(1)}|V|)$ time, where $\tau$ is the time taken to evaluate the function.

Stoer and Wagner [19] and Frank [2] independently have presented an algo-
rithm that finds a minimum cut of a graph $G = (V, E)$ in $O(|E||V| + |V|^2 \log |V|)$
time. Their algorithms are based on Nagamochi and Ibaraki's algorithm [15]
which finds a minimum cut of an undirected graph. Queyranne [17] developed a
faster algorithm to find a minimizer in a special case of a submodular system.
This algorithm was proposed to find a minimizer of a symmetric submodular sys-
tem $\mathcal{S} = (V, f)$. It is a generalization of Stoer and Wagner's algorithm [19] and
runs in $O(|V|^3)$ time. This algorithm, similar to Stoer and Wagner's algorithm
uses pendant pairs to obtain a minimizer of a symmetric submodular system.

For a given weighted undirected graph $G = (V, E)$, Gomory and Hu constructed a weighted tree, named as Gomory Hu tree [5]. By using a Gomory Hu tree of the graph $G$, one can solve the all pairs minimum st-cut problem with $|V| - 1$ calls to the maximum flow subroutine instead of the $\binom{|V|}{2}$ calls. Goemans and Ramakrishnan [4] illustrated that for every symmetric submodular system, there exists a Gomory-Hu tree. It is worth to mention that, there is neither an algorithm to construct a Gomory Hu tree of a symmetric submodular system by using pendant pairs nor any method to obtain pendant pairs of a symmetric submodular system by using a Gomory Hu tree of it.

In this paper, we obtain a Gomory Hu tree of a contraction of a symmetric
submodular system $\mathcal{S} = (V, f)$, under some subsets of $V$ only by using a Go-
mory Hu tree of $\mathcal{S}$. In other words, without solving any minimum st-separator
problem of the contracted system, we obtain a Gomory Hu tree of it only by
contracting the Gomory Hu tree of the original system. Furthermore, we obtain
some pendant pairs of a symmetric submodular system $\mathcal{S}$ and its contractions
by using a Gomory Hu tree of $\mathcal{S}$.

The outline of this paper is as follows. Section 2 provides preliminaries and
basic definitions. In Section 3, we obtain some pendant pairs of a symmetric
submodular system by using a Gomory Hu tree of the system. In Section 4, we
construct a Gomory Hu tree of a contracted system by using a Gomory Hu tree
of the original system.
## 2 Preliminaries

Let $V$ be a finite nonempty set. A function $f: 2^V \to \mathbb{R}$ is called a set function on $V$. For every $X \subseteq V$, $x \in X$ and $y \in V \setminus X$, we use $X+y$ and $X-x$ instead of $X \cup \{y\}$ and $X \setminus \{x\}$, respectively. Also, for $x \in V$ we use $f(x)$ instead of $f(\{x\})$.

A pair $S = (V, f)$, is called a system if $f$ is a set function on $V$. A system $S = (V, f)$ is called a submodular system if for all $X, Y \subseteq V$, we have

$$f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y). \quad (2)$$

Furthermore, it is called a symmetric system if for every $X \subseteq V$, we have

$$f(X) = f(V \setminus X). \quad (3)$$

Consider a symmetric submodular system $S = (V, f)$. Suppose that $A$ and $B$ are two disjoint subsets of $V$. A subset $X \subseteq V$ is called an AB-separator in $S$, if $X \cap (A \cup B) = A$ or $X \cap (A \cup B) = B$. Let $\Gamma(A, B)$ denote the set of all AB-separators in $S$. A subset $X \in \Gamma(A, B)$ is called a minimum AB-separator in $S$ if $f(X) = \min_{Y \in \Gamma(A, B)} f(Y)$. If $A$ and $B$ are singletons $\{a\}$ and $\{b\}$, then we use ab-separator and $\Gamma(a, b)$ instead of $\{a\}\{b\}$-separator and $\Gamma(\{a\}, \{b\})$, respectively.

Let $G = (V, E)$ be a weighted undirected graph with the weight function $w: E \to \mathbb{R}^+ \cup \{0\}$. Suppose that $X$ is a nonempty proper subset of $V$. The set of all edges connecting $X$ to $V \setminus X$, is called the cut associated with $X$ and is denoted by $\delta(X)$. The capacity of $\delta(X)$ is denoted by $C(X)$ and defined by

$$C(X) = \sum_{e \in \delta(X)} w(e). \quad (4)$$

By setting $C(\emptyset) = C(V) = 0$, $(V, C)$ is a symmetric submodular system [14]. For two distinct vertices $u$ and $v$ of $G$, every minimum $uv$-separator of $(V, C)$ is a minimum $uv$-cut of $G$.

Let $T = (V, F)$ be a tree and $uv$ be an arbitrary edge of it. By $T-uv$, we mean the forest obtained from $T$ by removing $uv$. The set of vertices of two components of $T-uv$ which respectively contain $u$ and $v$, is denoted by $V_u(T-uv)$ and $V_v(T-uv)$. Also, for $uv \in F$, define $\mathcal{F}_u(T-uv) = \{X|u \in X \subseteq V_u(T-uv)\}$, $\mathcal{F}_v(T-uv) = \{X|v \in X \subseteq V_v(T-uv)\}$.

Suppose that $X$ is a nonempty subset of vertices of a given graph $G = (V, E)$. We denote by $G_{>X}$ the graph obtained from $G$ by contracting all the vertices in $X$ into a single vertex.

Let $S = (V, f)$ be a symmetric submodular system. Suppose that $T = (V, F)$ is a weighted tree with the weight function $w: E \to \mathbb{R}^+$. If for all $u, v \in V$, the minimum weight of the edges on the path between $u$ and $v$ in $T$ is equal to minimum $uv$-separator in $S$, then $T$ is called a flow equivalent tree of $S$. Also, we say that $T$ has the cut property with respect to $S$ if $w(e) = f(V_u(T-uv)) = f(V_v(T-uv))$ for every $e = uv \in F$. A flow equivalent tree of $S$ is called a Gomory Hu tree of $S$ if it has cut property with respect to $S$.
Consider a system $\mathcal{S} = (V, f)$. A pair of elements $(x, y)$ of $V$ is called a pendant pair for $\mathcal{S}$, if $\{y\}$ is a minimum $xy$-separator in $\mathcal{S}$.

Let $\mathcal{S} = (V, f)$ be a symmetric submodular system. Suppose that $\rho = (v_1, v_2, \cdots, v_{|V|})$ is an ordering of the elements of $V$, where $v_1$ can be chosen arbitrarily. If for all $2 \le i \le j \le |V|$, we have

$$f(V_{i-1} + v_i) - f(v_i) \le f(V_{i-1} + v_j) - f(v_j), \quad (5)$$

where $V_i = \{v_1, v_2, \cdots, v_i\}$, then $\rho$ is called a maximum adjacency ordering (MA-ordering) of $\mathcal{S}$.

For a symmetric submodular system $\mathcal{S} = (V, f)$, Queyranne [17] showed that the last two elements $(v_{|V|-1}, v_{|V|})$ of an MA-ordering of $\mathcal{S}$, is a pendant pair of this system.

Let $\mathcal{S} = (V, f)$ be a system and $X$ be an arbitrary subset of $V$. By $\varphi(X)$, we mean a single element obtained by unifying all elements of $X$. The contraction of $\mathcal{S}$ with respect to a subset $A \subseteq V$ is denoted by $\mathcal{S}_A = (V_A, f_A)$ and defined by $V_A = (V \setminus A) + \varphi(A)$ and

$$f_A(X) = \begin{cases} f(X) & \text{if } \varphi(A) \notin X \\ f((X - \varphi(A)) \cup A) & \text{if } \varphi(A) \in X. \end{cases} \quad (6)$$

Suppose that $A$ and $B$ are two nonempty disjoint subsets of $V$. We denote by $(\mathcal{S}_A)_B$, the contraction of $\mathcal{S}_A$ with respect to $B$.

### 3 Obtaining Pendant Pairs from a Gomory Hu tree

Stoer and Wagner [19] obtained a pendant pair of a weighted undirected graph $G = (V, E)$ by using MA-ordering in $O(|E| + |V| \log |V|)$ time. By generalizing their algorithm to a symmetric submodular system $\mathcal{S} = (V, f)$, Queyranne [17] obtained a pendant pair of this system in $O(|V|^2)$ time.

In this section, by using the fact that there exists a Gomory Hu tree for a symmetric submodular system $\mathcal{S} = (V, f)$, we obtain some pendant pairs of it from a Gomory Hu tree of this system. Also, we show that a Gomory Hu tree of a symmetric submodular system can be constructed by pendant pairs. Firstly, we prove the following lemma.

**Lemma 1.** Let $T = (V, F)$ be a flow equivalent tree of a symmetric submodular system $\mathcal{S} = (V, f)$ with the weight function $w : E \mapsto \mathbb{R}^+$. If $e = uv$ is an arbitrary edge of $T$, then for every $A \in \mathcal{F}_u(T - uv)$ and $B \in \mathcal{F}_v(T - uv)$, we have $w(e) \le \min\{f(X)|X \in \Gamma(A, B)\}$.

*Proof.* Since $T$ is a flow equivalent tree of $\mathcal{S}$, then the value of a minimum $uv$-separator in $\mathcal{S}$ is equal to $w(e)$. In other words $w(e) = \min\{f(X)|X \in \Gamma(u, v)\}$. Since $\mathcal{F}_u(T - uv)$ and $\mathcal{F}_v(T - uv)$ are two subsets of $\Gamma(u, v)$, then $w(e) \le \min\{f(X)|X \in \Gamma(A, B)\}$.
**Theorem 1.** Let $T = (V, F)$ be a Gomory Hu tree of a symmetric submodular system $S = (V, f)$ with the weight function $w : E \to \mathbb{R}^+$. If $e = uv$ is an arbitrary edge of $T$, then for every $A \in \mathcal{F}_u(T - uv)$ and $B \in \mathcal{F}_v(T - uv)$, $V_v(T - uv)$ is a minimum $AB$-separator in $S$.

*Proof.* Since $T$ has the cut property, then $w(e) = f(V_v(T - uv))$. Now, according to Lemma 1 we have $f(V_v(T - uv)) \le \min\{f(X)|X \in \Gamma(A, B)\}$. On the other hand, $V_v(T - uv)$ is one of the elements of $\Gamma(A, B)$ then $f(V_v(T - uv)) = \min\{f(X)|X \in \Gamma(A, B)\}$, and the proof is completed.

The following theorem is immediate from Theorem 1.

**Theorem 2.** Let $T = (V, F)$ be a Gomory Hu tree of a symmetric submodular system $S = (V, f)$. If $e = uv$ is an arbitrary edge of $T$, then $(\varphi(A), \varphi(V_v(T - uv)))$ for every $A \in \mathcal{F}_u(T - uv)$ is a pendant pair of $(S_A)_{V_v(T - uv)}$.

Theorem 2 shows that every Gomory Hu tree of a symmetric submodular system can be obtained by using pendant pairs. We know that every Gomory Hu tree of a symmetric submodular system $S$ is a flow equivalent tree having the cut property. We show by an example that Theorem 2 is not necessarily true for every flow equivalent tree of $S$. Let $V = \{1, 2, 3, 4\}$. Consider the symmetric submodular system $S = (V, f)$ presented in Table 1.

<table><caption>**Table 1.** A symmetric submodular system $S = (V, f)$.</caption><thead><tr><th>A</th><th>{1}</th><th>{2}</th><th>{3}</th><th>{4}</th><th>{1, 2}</th><th>{1, 3}</th><th>{1, 4}</th><th>V</th></tr></thead><tbody><tr><td>f(A) = f(V\A)</td><td>4</td><td>6</td><td>3</td><td>5</td><td>4</td><td>5</td><td>9</td><td>0</td></tr></tbody></table>

It can be shown that the tree $T = (V, f)$ depicted in Figure 1 is a flow equivalent tree of $S$. Suppose that $w : E \to \mathbb{R}^+$ is the weight function of $T$. By considering the edge $e = 24$ of $T$, we have $V_4(T - 24) = \{4\}$. Now, choose the element $\{2\}$ from $\mathcal{F}_2(T - 24)$. According to Figure 1, $\{4\}$ is a minimum 24-cut and $w(24) = 4$. Since $T$ is a flow equivalent tree of $S$, then the value of minimum 24-separator in $S$ is equal to 4. However, in the given system we have $f(\{4\}) = 5$. Therefore, $(2, 4)$ cannot be a pendant pair of $S$.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Flow Equivalent tree of $S$.</figcaption></figure>

**Theorem 3.** Let $T = (V, F)$ be a flow equivalent tree of a symmetric submodular system $S = (V, f)$ with the weight function $w : F \to \mathbb{R}^+$. If for every edge $e = uv$
of $T$, there exists a set $A \in \mathcal{F}_u(T - uv)$ such that $(\varphi(A), \varphi(V_v(T - uv)))$ is a pendant pair of $(S_A)_{V_v(T - uv)}$, then $T$ is a Gomory Hu tree.

*Proof.* Since for every $e = uv$ of $T$, there exists a subset $A$ in $\mathcal{F}_u(T - uv)$, that $(\varphi(A), \varphi(V_v(T - uv)))$ is a pendant pair of $(S_A)_{V_v(T - uv)}$ then $w(e) = f(V_v(T - uv))$. Thus, $T$ has the cut property. Therefore, $T$ is a Gomory Hu tree of $S$.

In the rest of this section, we will prove some properties of pendant pairs of a system.

**Theorem 4.** Let $(s, l)$ be a pendant pair of a system $S = (V, f)$. For every $A \subseteq V\{s, l\}$, $(s, l)$ is a pendant pair of $S_A$.

*Proof.* Since $(s, l)$ is a pendant pair of $S$, then $f(l) = \min\{f(X)|X \in \Gamma(s, l)\}$. From (6) we have $f(l)=f_A(l) = \min\{f_A(X)|X \in \Gamma(s, l)\}$.

Thus, $(s, l)$ is a pendant pair of $S_A$. The proof is completed.

Note that, the converse of Theorem 4 is not generally true. Consider the given system in Table 1. Table 2 contains MA-orderings of $S$ and $S_{\{1,3\}}$ and also pendant pairs, obtained from these MA-orderings.

<table><caption>**Table 2.** MA-orderings of $S$ and $S_{\{1,3\}}$.</caption><thead><tr><th>system</th><th>MA-ordering</th><th>Pendant Pair</th></tr></thead><tbody><tr><td>$S$</td><td>4, 2, 1, 3</td><td>(1, 3)</td></tr><tr><td>$S_{\{1,3\}}$</td><td>13, 2, 4</td><td>(2, 4)</td></tr></tbody></table>

It can be observed that $(2, 4)$ is a pendant pair of $S_{\{1,3\}}$; however, it is not a pendant pair of $S$.

**Proposition 1.** If $(s, l)$ is a pendant pair of a system $S = (V, f)$, then $(l, s)$ is a pendant pair of $S$ iff $f(l) = f(s)$.

*Proof.* Let $(l, s)$ be a pendant pair of $S$. Thus, $f(l) = \min\{f(X)|X \in \Gamma(s, l)\}$. Since $(s, l)$ is also a pendant pair of $S$, then $f(s) = f(l)$. Now, suppose that $f(s) = f(l)$. Since $(s, l)$ is a pendant pair of $S$, then $(l, s)$ is also a pendant pair of $S$.

# 4 Gomoru Hu Tree of the Contraction of a System

Let $T = (V, F)$ be a tree. A subset $X \subseteq V$ is called a *T-connected* subset of $V$, if the graph induced by $X$ in $T$ is a subtree. The following theorem shows that by having a flow equivalent tree $T$ of a symmetric submodular system $S = (V, f)$, we can easily obtain a flow equivalent tree of $S_X$ for every T-connected subset of $V$.
**Theorem 5.** Let $T = (V, F)$ be a flow equivalent tree of a symmetric submodular system $S = (V, f)$. If $X$ is a $T$-connected subset of $V$, then $T_{>X}^-$ is a flow equivalent tree of $S_X = (V_X, f_X)$.

*Proof.* Let $u$ and $v$ be two distinct elements of $V_X$. Consider the path $P_{uv}$ connecting $u$ and $v$ in $T$. Suppose that $T' = (V', F')$ is the induced subtree by $X$ in $T$. Let $E'$ be the set of edges in $P_{uv}$ with the minimum weight. If $E' \not\subseteq F'$, then there is nothing to prove. Now, suppose that $E'$ is a subset of $F'$. Assume that $m_1 = \min\{f_X(A) | A \in \Gamma(u, \varphi(X))\}$, $m_2 = \min\{f_X(A) | A \in \Gamma(\varphi(X), v)\}$ and $m^* = \min\{f_X(A) | A \in \Gamma(u, v)\}$. Obviously, the values of the minimum $u\varphi(X)$-cut, the minimum $\varphi(X)v$-cut and the minimum $uv$-cut in tree $T_{>X}^-$ are equal to $m_1, m_2$ and $\min\{m_1, m_2\}$, respectively. Thus, to show that $T_{>X}^-$ is a flow equivalent tree of $S_X$ it suffices to prove that $m^* = \min\{m_1, m_2\}$. Let $T'$ be a flow equivalent tree of $S_X$ and $P'_{uv}$ be a path connecting $u$ and $v$ in $T'$. Now, we have two cases: case (i), $\varphi(X)$ is appeared in $P'_{uv}$. Therefore, the value of $uv$-separator in $S_X$ is equal to $\min\{m_1, m_2\}$ which is equal to the value of minimum $uv$-cut in $T_{>X}^$. Case (ii), if $\varphi(X)$ is not appeared in $P'_{uv}$, then we can easily conclude that the value of minimum $uv$-cut in $T'$ and $T_{>X}^-$ are equal. The proof is completed.

**Theorem 6.** Let $T = (V, F)$ be a Gomory Hu tree of a symmetric submodular system $S = (V, f)$. If $X$ is a $T$-connected subset of $V$, then $T_{>X}^-$ is a Gomory Hu tree of $S_X = (V_X, f_X)$.

*Proof.* According to Theorem 5, $T_{>X}^-$ is a flow equivalent of $S_X$. Furthermore, from (6), $T_{>X}^-$ has the cut property. Then, $T_{>X}^-$ is a Gomory Hu tree of $S_X$.

Then, by having a Gomory Hu tree of a symmetric submodular system $S = (V, f)$, we can find a Gomory Hu tree of the contracted system, with respect to a connected set $X$, without finding any minimum $st$-separators in $S_X$. Also, we can deduce that $T_{>V_v(T-uv)}$ is a Gomory Hu tree of $S_{V_v(T-uv)}$.

**Corollary 1.** Let $T = (V, f)$ be a Gomory Hu tree of a symmetric submodular system $S = (V, f)$ and $uv$ be an arbitrary edge of $T$. For every $A \in \mathcal{F}_u(T-uv)$, for which $A$ is a connecting set in $T$, the tree $T_{>A \cup V_v(T-uv)}$ is a Gomory Hu tree of $(S_A)_{V_v(T-uv)}$.

# 5 Conclusion

In this paper, we obtained some pendant pairs of a symmetric submodular system by using its Gomory Hu tree. Furthermore, for a contraction of $S$ with respect to a connected set, we constructed a Gomory Hu tree only by contracting the connected set in Gomory Hu tree of $S$.

**Acknowledgements** The authors would like to thank the anonymous referees for their helpful suggestions and comments to improve the paper.
References

1. Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts. IEEE Transactions on pattern analysis and machine intelligence. 2001 Nov;23(11):1222-39.

2. Frank A. On the edge-connectivity algorithm of Nagamochi and Ibaraki. Laboratoire Artemis, IMAG, Universit J. Fourier, Grenoble. 1994 Mar.

3. Fujishige S. Submodular functions and optimization. Elsevier; 2005 Jul 26.

4. Goemans MX, Ramakrishnan VS. Minimizing submodular functions over families of sets. Combinatorica. 1995 Dec 1;15(4):499-513.

5. Gomory RE, Hu TC. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics. 1961 Dec;9(4):551-70.

6. Grtschel M, Lovsz L, Schrijver A. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica. 1981 Jun 1;1(2):169-97.

7. Iwata S, Fleischer L, Fujishige S. A combinatorial strongly polynomial algorithm for minimizing submodular functions. Journal of the ACM (JACM). 2001 Jul 1;48(4):761-77.

8. Kohli P, Kumar MP, Torr PH. P3 Beyond: Move Making Algorithms for Solving Higher Order Functions. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2009 Sep;31(9):1645-56.

9. Kohli P, Torr PH. Dynamic graph cuts and their applications in computer vision. InComputer Vision 2010 (pp. 51-108). Springer Berlin Heidelberg.

10. Lee YT, Sidford A, Wong SC. A faster cutting plane method and its implications for combinatorial and convex optimization. InFoundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on 2015 Oct 17 (pp. 1049-1065). IEEE.

11. Lin H, Bilmes J. An application of the submodular principal partition to training data subset selection. InNIPS workshop on Discrete Optimization in Machine Learning 2010 Dec.

12. Lin H, Bilmes JA. Optimal Selection of Limited Vocabulary Speech Corpora. In INTERSPEECH 2011 Aug (pp. 1489-1492).

13. Lovsz L, Grtschel M, Schrijver A. Geometric algorithms and combinatorial optimization. Berlin: Springer-Verlag. 1988;33:34.

14. Nagamochi H, Ibaraki T. Algorithmic aspects of graph connectivity. New York: Cambridge University Press; 2008 Sep 8.

15. Nagamochi H, Ibaraki T. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics. 1992 Feb;5(1):54-66.

16. Orlin JB. A faster strongly polynomial time algorithm for submodular function minimization. InInternational Conference on Integer Programming and Combinatorial Optimization 2007 Jun 25 (pp. 240-251). Springer Berlin Heidelberg.

17. Queyranne M. Minimizing symmetric submodular functions. Mathematical Programming. 1998 Jun 1;82(1-2):3-12.

18. Schrijver A. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B. 2000 Nov 30;80(2):346-55.

19. Stoer M, Wagner F. A simple min-cut algorithm. Journal of the ACM (JACM). 1997 Jul 1;44(4):585-91.

20. Wan PJ, Clinescu G, Li XY, Frieder O. Minimum-energy broadcasting in static ad hoc wireless networks. Wireless Networks. 2002 Nov 1;8(6):607-17.