✦ LIBER ✦

Balanced graphs and network flows

✍ Scribed by Penrice, Stephen G.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 64 KB
Volume: 29
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199703)29:2<77::aid-net1>3.0.co;2-8

No coin nor oath required. For personal study only.

✦ Synopsis

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 combined to form a larger balanced graph. In particular, we show that edge-transitive graphs and complete m-partite graphs are balanced, that a product or lexicographic product of balanced graphs is balanced, and that the normal product of a balanced graph and a regular graph is balanced.

📜 SIMILAR VOLUMES

Balanced network flows. VI. Polyhedral d

Balanced network flows. VI. Polyhedral descriptions

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

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

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

Strongly balanced graphs and random grap

Strongly balanced graphs and random graphs

✍ Andrzej Ruciński; Andrew Vince 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 455 KB

The concept of strongly balanced graph is introduced. It is shown that there exists a strongly balanced graph with u vertices and e edges if and only if I s u -1 s e s ( 2 " ) . This result is applied to a classic question of Erdos and Renyi: What is the probability that a random graph on n vertices