Metrics and undirected cuts

DOI10.1007/BF01586090zbMath0565.90016MaRDI QIDQ3680585

Alexander V. Karzanov

Publication date: 1985

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

undirected graphmulticommodity flowcut-metricsnonnegative integer-valued lengths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)

Related Items (16)

Applications of cut polyhedra. II ⋮ Zero-one completely positive matrices and the \(\mathcal A(R, S)\) classes ⋮ Finite metrics in switching classes ⋮ On fractional multicommodity flows and distance functions ⋮ Distances and cuts in planar graphs ⋮ A \(T_X\)-approach to some results on cuts and metrics ⋮ Metric packing for \(K_ 3 + K_ 3\) ⋮ The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds ⋮ Short proofs on multicommodity flows and cuts ⋮ Facets for the cut cone. I ⋮ Half-integral five-terminus flows ⋮ Sums of cuts and bipartite metrics ⋮ Hypercube embedding of generalized bipartite metrics ⋮ Fullerenes and coordination polyhedra versus half-cube embeddings ⋮ Packings of cuts realizing distances between certain vertices in a planar graph ⋮ \(\ell_ 1\)-rigid graphs

Cites Work

• The ellipsoid method and its consequences in combinatorial optimization
• A two-commodity cut theorem
• Four-terminus flows
• On the Extreme Rays of the Metric Cone
• On Two Commodity Network Flows
• Multi-Commodity Network Flows
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Metrics and undirected cuts