A characterization of minimizable metrics in the multifacility location problem

DOI10.1006/eujc.1999.0378zbMath0958.05045OpenAlexW2064393153MaRDI QIDQ1582478

Alexander V. Karzanov, Victor Chepoi, Hans-Jürgen Bandelt

Publication date: 30 March 2001

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

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

zbMATH Keywords

metricdistancecoincidenceframemultifacility location problemorientablesemi-metrichereditary modular

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Metric spaces, metrizability (54E35) Paths and cycles (05C38) Discrete location and assignment (90B80) Structural characterization of families of graphs (05C75) Distance in graphs (05C12)

Related Items (7)

Hard cases of the multifacility location problem ⋮ One more well-solved case of the multifacility location problem ⋮ On tight spans for directed distances ⋮ Metric packing for \(K_ 3 + K_ 3\) ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ Tight spans of distances and the dual fractionality of undirected multiflow problems ⋮ The tight span of an antipodal metric space. I: combinatorial properties

Cites Work

• Unnamed Item
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Networks with Condorcet solutions
• Hereditary modular graphs
• Minimum 0-extensions of graph metrics
• Six theorems about injective metric spaces
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• Modular Interval Spaces
• The Complexity of Multiterminal Cuts

This page was built for publication: A characterization of minimizable metrics in the multifacility location problem