Stochastic embeddings of graphs into trees

DOI10.1007/S43037-024-00373-7MaRDI QIDQ6613290zbMATH OpenFDO

Authors Th. Schlumprecht, Garrett Tresch

Publication date 2 October 2024

Published in Banach Journal of Mathematical Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S43037-024-00373-7

zbMATH Keywords

distortionslashpowersstochastic embeddingstrees

Mathematics Subject Classification ID

Trees (05C05) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Low-Distortion Embeddings of Trees
• scientific article; zbMATH DE number 2084288
• scientific article; zbMATH DE number 1954393
• A tight upper bound on the probabilistic embedding of series-parallel graphs
• Low distortion Euclidean embeddings of trees

Cites work

• A framework for solving VLSI graph layout problems
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A tight bound on approximating arbitrary metrics by tree metrics
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Analysis on Laakso graphs with application to the structure of transportation cost spaces
• Coarse differentiation and multi-flows in planar graphs
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Steiner points in tree metrics don't (really) help
• Stochastic approximation of lamplighter metrics
• Wasserstein distance and metric trees

Cited in

(1)

• Hyperbolic metric spaces and stochastic embeddings

This page was built for publication: Stochastic embeddings of graphs into trees

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