The Complexity of Metric Realization

DOI10.1137/0401051MaRDI QIDQ3815539zbMATH OpenOpenAlexFDO

Authors Peter 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

discrete metric realizationgraph with minimum total edge-lengthNP- completeshortest path

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 975398
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• A constructive algorithm for realizing a distance matrix
• Optimal realizations of two-dimensional, totally-decomposable metrics
• The metric cutpoint partition problem

Cited in

(18)

• Optimal realizations of generic five-point metrics
• Some personal views on the current state and the future of locational analysis
• Distance realization problems with applications to internet tomography
• Distance matrices on the \textit{H-join} of graphs: a general result and applications
• Characterization of realizable space complexities
• Optimal realizations and the block decomposition of a finite metric space
• Distance spectra of graphs: a survey
• Recognizing and realizing cactus metrics
• Optimal realizations of two-dimensional, totally-decomposable metrics
• On the Complexity of Metric Dimension
• Injective optimal realizations of finite metric spaces
• scientific article; zbMATH DE number 1962827 (Why is no real title available?)
• Tree reconstruction from partial orders
• On a class of metrics related to graph layout problems
• The metric cutpoint partition problem
• A constructive algorithm for realizing a distance matrix
• Compatible decompositions and block realizations of finite metrics
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3815539)