✦ LIBER ✦

A simple minimum T-cut algorithm

✍ Scribed by Romeo Rizzi

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 119 KB
Volume: 129
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(03)00182-3

No coin nor oath required. For personal study only.

✦ Synopsis

We give a simple algorithm for ÿnding a minimum T -cut. At present, all known e cient algorithms for this problem go through the computation of a Gomory-Hu tree. While our algorithm bases on the same fundamental properties of uncrossing as the previous methods, still it provides an ad hoc solution. This solution is easier to implement and faster to run. Our results extend to the whole of symmetric submodular functions.

📜 SIMILAR VOLUMES

A faster parametric minimum-cut algorith

A faster parametric minimum-cut algorithm

✍ Dan Gusfield; Éva Tardos 📂 Article 📅 1994 🏛 Springer 🌐 English ⚖ 842 KB

A Simple and Fast Min-Cut Algorithm

✍ Michael Brinkmeier 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 488 KB

Implementing an efficient minimum capaci

Implementing an efficient minimum capacity cut algorithm

✍ Hiroshi Nagamochi; Tadashi Ono; Toshihide Ibaraki 📂 Article 📅 1994 🏛 Springer-Verlag 🌐 English ⚖ 900 KB

Practical Performance of Efficient Minim

Practical Performance of Efficient Minimum Cut Algorithms

✍ M. Jünger; G. Rinaldi; S. Thienel 📂 Article 📅 2000 🏛 Springer 🌐 English ⚖ 544 KB

A Simple Algorithm for the Planar Multiw

A Simple Algorithm for the Planar Multiway Cut Problem

✍ Wei-Chang Yeh 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 95 KB

The traditional min-cut problem involves finding a cut with minimum weight between two specified vertices. The planar multiway cut problem is a NP-hard generalization of the min-cut problem. It involves separating a weighted planar graph with k specified vertices into k components such that the tota

An efficient algorithm for the minimum c

An efficient algorithm for the minimum capacity cut problem

✍ M. Padberg; G. Rinaldi 📂 Article 📅 1990 🏛 Springer-Verlag 🌐 English ⚖ 757 KB