The Complexity of Metric Realization

DOI10.1137/0401051zbMath0664.68071OpenAlexW2023542709MaRDI QIDQ3815539

Peter M. Winkler

Publication date: 1988

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0401051

zbMATH Keywords

shortest pathNP- completediscrete metric realizationgraph with minimum total edge-length

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Metric spaces, metrizability (54E35)

Related Items (12)

Tree reconstruction from partial orders ⋮ A constructive algorithm for realizing a distance matrix ⋮ Injective optimal realizations of finite metric spaces ⋮ Compatible decompositions and block realizations of finite metrics ⋮ Distance spectra of graphs: a survey ⋮ Distance matrices on the \textit{H-join} of graphs: a general result and applications ⋮ The metric cutpoint partition problem ⋮ Optimal realizations and the block decomposition of a finite metric space ⋮ Recognizing and realizing cactus metrics ⋮ Optimal realizations of generic five-point metrics ⋮ Some personal views on the current state and the future of locational analysis ⋮ Optimal realizations of two-dimensional, totally-decomposable metrics

This page was built for publication: The Complexity of Metric Realization