Optimum Branching Systems

20 mars 19

Mercredi 20 Mars 2019, 14h, en salle B112.

Jack Edmonds

Abstract :

The "Optimum Branching Systems" problem is given a digraph G, specified root nodes r(i), and a cost for each edge of G, find a least cost collection of edge-disjoint directed spanning trees in G rooted respectively at the nodes r(i).

There is  a polynomial time algorithm for this, based on several of my favorite topics, mainly about matroids. It includes but apparently does not reduce to mincost flow.  Several books on combinatorial optimization treat the topics without the application.