Minimum 0-extensions of graph metrics

DOI10.1006/eujc.1997.0154zbMath0894.90147OpenAlexW2055636480MaRDI QIDQ1378296

Alexander V. Karzanov

Publication date: 16 June 1998

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/eujc.1997.0154

zbMATH Keywords

polynomial time algorithmNP-hardnessminimum 0-extension problemminimum cut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)

Related Items (26)

Hard cases of the multifacility location problem ⋮ Metric extension operators, vertex sparsifiers and Lipschitz extendability ⋮ One more well-solved case of the multifacility location problem ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ On tight spans for directed distances ⋮ The vertex \(k\)-cut problem ⋮ A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case ⋮ Making doubling metrics geodesic ⋮ Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees ⋮ Unnamed Item ⋮ Metric packing for \(K_ 3 + K_ 3\) ⋮ Bounded fractionality of the multiflow feasibility problem for demand graph \(K_3 + K_3\) and related maximization problems ⋮ Graphs of some CAT(0) complexes ⋮ On duality and fractionality of multicommodity flows in directed networks ⋮ Unnamed Item ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ Minimum 0-extension problems on directed metrics ⋮ A simple algorithm for the multiway cut problem ⋮ Weakly Modular Graphs and Nonpositive Curvature ⋮ Retracting Graphs to Cycles ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ Tight spans of distances and the dual fractionality of undirected multiflow problems ⋮ Metrics with finite sets of primitive extensions ⋮ A characterization of minimizable metrics in the multifacility location problem ⋮ On Lipschitz extension from finite subsets

This page was built for publication: Minimum 0-extensions of graph metrics