Computational complexity of combinatorial distance matrix realisation

DOI10.1007/978-3-031-92932-8_4MaRDI QIDQ6902210zbMATH OpenFDO

Authors David L. Fairbairn, George B. Mertzios, Norbert Peyerimhoff

Publication date 11 November 2025

Full work available at URL https://doi.org/10.1007/978-3-031-92932-8_4

zbMATH Keywords

distance matrixgraph colourabilitygraph realisationNP-completenesspolynomial-time algorithm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A fast algorithm for constructing trees from distance matrices
• Approximating some network design problems with node costs
• Distance matrix of a graph and its realizability
• Distance realization problems with applications to internet tomography
• Generalized network design problems.
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 3243264 (Why is no real title available?)
• On optimal realizations of finite metric spaces by graphs
• Reducibility among combinatorial problems
• The multicolored graph realization problem
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces

This page was built for publication: Computational complexity of combinatorial distance matrix realisation

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