Finding thet-join structure of graphs

DOI10.1007/BF02592020MaRDI QIDQ3030603zbMATH OpenOpenAlexFDO

Authors András Sebö

Publication date 1986

Published in Mathematical Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02592020

zbMATH Keywords

chinese postmanmatchingsmaximum packing of t-cutsminimum t-joinplanar multicommodity flowspolynomial time algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Programming involving graphs or networks (90C35)

Recommendations

• Fractional Packing ofT-Joins
• On shortest T-joins and packing T-cuts
• A quick proof of Seymour's theorem on t-joins
• Two-trees optimal \(T\)-join and integral packing of \(T\)-cuts
• Tight integral duality gap in the Chinese postman problem

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

(7)

• 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

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

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