𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Multiterminal flows and cuts

✍ Scribed by David Hartvigsen; François Margot

Book ID
107918309
Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
296 KB
Volume
17
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Crossing properties of multiterminal cut
Crossing properties of multiterminal cuts
✍ Easley, Robert F.; Hartvigsen, David 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

Gomory and Hu proved the following classical result: For any graph with nonnegative edge weights, there exists a collection of noncrossing cuts that contains a minimum cut for every pair of nodes. In this paper, we show how this result generalizes for a natural multiterminal cut problem. We also sho

The node multiterminal cut polyhedron
The node multiterminal cut polyhedron
✍ Yu, Bo; Cheriyan, Joseph 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB

Given an undirected graph G Å (V ʜ A, E), where A is a set of terminal nodes and V is a set of nonterminal nodes, a node multiterminal cut is a set of nonterminal nodes whose deletion disconnects every pair of terminal nodes. We study the node multiterminal cut polyhedron, denoted P(G, A). We give s

Characterizing Multiterminal Flow Networ
Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth
✍ Torben Hagerup; Jyrki Katajainen; Naomi Nishimura; Prabhakar Ragde 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 417 KB

We show that if a flow network has k inputÂoutput terminals (for the traditional maximum-flow problem, k=2), its external flow pattern (the possible values of flow into and out of the terminals) has two characterizations of size independent of the total number of vertices: a set of 2 k +1 inequaliti