𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Connectivity of submodular functions

✍ Scribed by James Oxley; Geoff Whittle

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
788 KB
Volume
105
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The notion of connectivity for submodular functions was introduced by Cunningham. This paper relates the connectivity of such a function f to that of certain submodular functions which are derived from j In particular, we prove a generalisation of the well-known matroid result that, for every element x of a connected matroid from M is connected.

M, either the deletion or contraction of x

πŸ“œ SIMILAR VOLUMES

Horn functions and submodular boolean fu
Horn functions and submodular boolean functions
✍ Oya Ekin; Peter L. Hammer; Uri N. Peled πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 953 KB

After providing a simple characterization of Horn functions (i.e., those Boolean functions that have a Horn DNF), we study in detail the special class of submodular functions. Every prime implicant of such a function involves at most one complemented and at most one uncomplemented variable, and base

Submodular function minimization
Submodular function minimization
✍ Satoru Iwata πŸ“‚ Article πŸ“… 2007 πŸ› Springer-Verlag 🌐 English βš– 302 KB
Submodular functions in graph theory
Submodular functions in graph theory
✍ AndrΓ‘s Frank πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 819 KB

Frank, A., Submodular functions in graph theory, Discrete Mathematics 111 (1993) 231-243. We describe various aspects of the use of submodular functions in graph theory. New proofs of theorems of Mader and of Tutte are provided as well as a new application on making a digraph k-edge-connected by ad