✦ LIBER ✦

Balanced network flows. VI. Polyhedral descriptions

✍ Scribed by Christian Fremuth-Paeger; Dieter Jungnickel

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 131 KB
Volume: 37
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.1015

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Balanced graphs and network flows

✍ Penrice, Stephen G. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB

A graph G is balanced if the maximum ratio of edges to vertices, taken over all subgraphs of G, occurs at G itself. This note uses the max-flow/min-cut theorem to prove a good characterization of balanced graphs. This characterization is then applied to some results on how balanced graphs may be com

Balanced network flows. II. Simple augme

Balanced network flows. II. Simple augmentation algorithms

✍ Fremuth-Paeger, Christian; Jungnickel, Dieter 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB

In previous papers, we discussed the fundamental theory of matching problems and algorithms in terms of a network flow model. In this paper, we present explicit augmentation procedures which apply to the wide range of capacitated matching problems and which are highly efficient for k-factor problems

Balanced network flows. V. Cycle-canceli

Balanced network flows. V. Cycle-canceling algorithms

✍ Christian Fremuth-Paeger; Dieter Jungnickel 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

Balanced network flows. III. Strongly po

Balanced network flows. III. Strongly polynomial augmentation algorithms

✍ Fremuth-Paeger, Christian; Jungnickel, Dieter 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB

We discuss efficient augmentation algorithms for the maximum balanced flow problem which run in O(nm 2 ) time. More explicitly, we discuss a balanced network search procedure which finds valid augmenting paths of minimum length in linear time. The algorithms are based on the famous cardinality match

Balanced network flows. IV. Duality and

Balanced network flows. IV. Duality and structure theory

✍ Christian Fremuth-Paeger; Dieter Jungnickel 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB

Maximum Balanced Flow in a Network

✍ Haggai Ilani; Michael Lomonosov 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 123 KB