✦ LIBER ✦

Parametric min-cuts analysis in a network

✍ Scribed by Y.P Aneja; R Chandrasekaran; K.P.K Nair

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 131 KB
Volume: 127
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(02)00496-1

No coin nor oath required. For personal study only.

✦ Synopsis

The all pairs minimum cuts problem in a capacitated undirected network is well known. Gomory and Hu showed that the all pairs minimum cuts are revealed by a min-cut tree that can be obtained by solving exactly (n -1) maximum ow problems, where n is the number of nodes in the network.

In this paper we consider ÿrst the problem of ÿnding parametric min-cuts for a speciÿed pair of nodes when the capacity of an arc i is given by min{bi; }, where is the parameter, ranging from 0 to ∞. Next we seek the parametric min-cuts for all pairs of nodes, and achieve this by constructing min-cut trees for at most 2m di erent values of , where m is the number of edges in the network.

📜 SIMILAR VOLUMES

Parametric analysis of overall min-cuts

Parametric analysis of overall min-cuts and applications in undirected networks

✍ Y.P. Aneja; R. Chandrasekaran; K.P.K. Nair 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 211 KB

The overall min-cut problem in a capacitated undirected network is well known. Recently Stoer and Wagner gave an elegant algorithm for finding such a cut. In this paper we present a parametric analysis of such a cut where the capacity of an arc {i, j } in the network is given by min{b ij , λ}, where

Minimum cuts in parametric networks

✍ F. A. Sharifov 📂 Article 📅 1994 🏛 Springer US 🌐 English ⚖ 402 KB

All-Pairs Min-Cut in Sparse Networks

✍ Srinivasa R Arikati; Shiva Chaudhuri; Christos D Zaroliagis 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 355 KB

Algorithms are presented for the all-pairs min-cut problem in bounded treewidth, planar, and sparse networks. The approach used is to preprocess the input n-vertex network so that afterward, the value of a min-cut between any two vertices can be efficiently computed. A tradeoff is shown between the

A Relaxation of a Min-Cut Problem in an

A Relaxation of a Min-Cut Problem in an Anisotropic Continuous Network

✍ R. Nozawa 📂 Article 📅 1999 🏛 Springer 🌐 English ⚖ 139 KB

Disjoint (s, t)-cuts in a network

✍ Donald K. Wagner 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 638 KB

A new min-cut problem with application t

A new min-cut problem with application to electric power network partitioning

✍ Arunabha Sen; Pavel Ghosh; Vijay Vittal; Bo Yang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 350 KB