Finding the t-join structure of graphs

From MaRDI portal





A polynomial time algorithm that determines a minimum t-join and a maximum packing of t-cuts, and a Gallai-Edmonds type structural decomposition of (G,t) pairs, independent of the running of the algorithm, are presented. (t-joins are generalizations of postman tours, matchings and paths, and t-cuts contain planar multicommodity flows as a special case.)











This page was built for publication: Finding the t-join structure of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3030603)