Distance realization problems with applications to internet tomography

DOI10.1006/jcss.2001.1785zbMath1006.68102OpenAlexW2096320713MaRDI QIDQ1604199

Ronald L. Graham, Mark Garrett, David F. Shallcross, Fan R. K. Chung

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2001.1785

zbMATH Keywords

graph optimization problemsdistance realization problems

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Metric violation distance: hardness and approximation, Reconstruction of graphs based on random walks, Near-Linear Query Complexity for Graph Inference, Vertex-weighted graphs: realizable and unrealizable domains, Extinction and asymptotic behavior of solutions for the \(\omega\)-heat equation on graphs with source and interior absorption, Injective optimal realizations of finite metric spaces, Smith normal form of a distance matrix inspired by the four-point condition, Topology reconstruction using time series data in telecommunication networks, Extinction and positivity of solutions of the \(p\)-Laplacian evolution equation on networks, Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem, Distance spectra of graphs: a survey, Reconstructing trees from subtree weights., The metric cutpoint partition problem, Searching for realizations of finite metric spaces in tight spans, Optimal realizations and the block decomposition of a finite metric space, Composed degree-distance realizations of graphs, Composed degree-distance realizations of graphs, A tropical interpretation of \(m\)-dissimilarity maps, Topology discovery of sparse random graphs with few participants, Tomography on Finite Graphs, Relaxed and approximate graph realizations, An algorithm for computing cutpoints in finite metric spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm and its role in the study of optimal graph realizations of distance matrices
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• On optimal realizations of finite metric spaces by graphs
• A fast algorithm for constructing trees from distance matrices
• An efficient PQ-graph algorithm for solving the graph-realization problem
• Submatrices of non-tree-realizable distance matrices
• The Steiner tree problem
• On graphs which contain all small trees
• A random graph model for massive graphs
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• Universal graphs and induced-universal graphs
• An Almost Linear-Time Algorithm for Graph Realization
• An Optimality Criterion for Graph Embeddings of Metrics
• The distance matrix of a graph and its tree realization
• Recognition of Tree Metrics
• Fast Parallel Recognition of Ultrametrics and Tree Metrics
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On Universal Graphs for Spanning Trees
• Distance matrix of a graph and its realizability
• Properties of the distance matrix of a tree
• A note on the tree realizability of a distance matrix