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.)
Recommendations
Cites work
- 2-Matchings and 2-covers of hypergraphs
- Covering directed and odd cuts
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 3231691 (Why is no real title available?)
- Matching, Euler tours and the Chinese postman
- On Odd Cuts and Plane Multicommodity Flows
- On the surface duality of linear graphs
- Paths, Trees, and Flowers
Cited in
(8)- Undirected distances and the postman-structure of graphs
- The Schrijver system of odd join polyhedra
- Las Vegas RNC algorithms for unary weighted perfect matching and \(T\)-join problems
- On shortest T-joins and packing T-cuts
- Approximation algorithms with constant ratio for general cluster routing problems
- scientific article; zbMATH DE number 3861220 (Why is no real title available?)
- T-joins in strongly connected hypergraphs
- Matchings: source, goal, and faithful companion
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)