✦ LIBER ✦

Generalizing the all-pairs min cut problem

✍ Scribed by David Hartvigsen

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 1017 KB
Volume: 147
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00233-9

No coin nor oath required. For personal study only.

✦ Synopsis

The all-pairs min cut (APMC) problem on a nonnegative edge-weighted graph is to find, for each pair of nodes, a min cut that separates the pair. Gomory and Hu (1961) presented a structural characterization of collections of cuts that solve the APMC problem. We show how the APMC problem can be generalized to matroids and we present several theorems that characterize the structure of solutions to this more general problem. The result of Gomory and Hu is a special case of one of these theorems. In particular, we find that the APMC problem is a matroid optimization problem.

📜 SIMILAR VOLUMES

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

The all-pairs quickest path problem

✍ D.T. Lee; E. Papadopoulou 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 625 KB

On the Exponent of the All Pairs Shortes

On the Exponent of the All Pairs Shortest Path Problem

✍ Noga Alon; Zvi Galil; Oded Margalit 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 900 KB

The upper bound on the exponent, |, of matrix multiplication over a ring that was three in 1968 has decreased several times and since 1986 it has been 2.376. On the other hand, the exponent of the algorithms known for the all pairs shortest path problem has stayed at three all these years even for t

An efficient algorithm for the All Pairs

An efficient algorithm for the All Pairs Suffix-Prefix Problem

✍ Dan Gusfield; Gad M. Landau; Baruch Schieber 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 385 KB

Subcubic Cost Algorithms for the All Pai

Subcubic Cost Algorithms for the All Pairs Shortest Path Problem

✍ T. Takaoka 📂 Article 📅 1998 🏛 Springer 🌐 English ⚖ 95 KB

On the All-Pairs-Shortest-Path Problem i

On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs

✍ R. Seidel 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 318 KB

We present an algorithm, APD, that solves the distance version of the all-pairs-shortest-path problem for undirected, unweighted \(n\)-vertex graphs in time \(O(M(n) \log n)\), where \(M(n)\) denotes the time necessary to multiply two \(n \times n\) matrices of small integers (which is currently kno