𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Submodular functions in graph theory

✍ Scribed by András Frank

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
819 KB
Volume
111
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 adding a minimum number of edges.

📜 SIMILAR VOLUMES

A Combinatorial Algorithm Minimizing Sub
A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time
✍ Alexander Schrijver 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 108 KB

We give a strongly polynomial-time algorithm minimizing a submodular function f given by a value-giving oracle. The algorithm does not use the ellipsoid method or any other linear programming method. No bound on the complexity of the values of f is needed to be known a priori. The number of oracle c

Extremal problems in graph theory
Extremal problems in graph theory
✍ Béla Bollobás 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB

## Abstract The aim of this note is to give an account of some recent results and state a number of conjectures concerning extremal properties of graphs.

Some problems in topological graph theor
Some problems in topological graph theory
✍ Jonathan L. Gross; Frank Harary 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English

## Abstract A list of 31 problems presented here reflects some of the main trends in topological graph theory.

A retraction problem in graph theory
A retraction problem in graph theory
✍ Alain Quilliot 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 563 KB

Given two graphs G=(X,E), H=(Y,F); If AcX and if f is a function from A to Y, we pose the problem of deciding if f can be extended into a homomorphism from G to H. We know how to solve this problem when H is, for instance, a tree, or a chordal graph. We give here a solution to this problem when g is