Finding thet-join structure of graphs

DOI10.1007/BF02592020zbMath0626.90090OpenAlexW2153374808MaRDI QIDQ3030603

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

polynomial time algorithmmatchingschinese postmanmaximum packing of t-cutsminimum t-joinplanar multicommodity flows

Mathematics Subject Classification ID

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

Related Items (5)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Covering directed and odd cuts
• On Odd Cuts and Plane Multicommodity Flows
• 2-Matchings and 2-covers of hypergraphs
• Matching, Euler tours and the Chinese postman
• On the surface duality of linear graphs
• Paths, Trees, and Flowers

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