Stochastic embeddings of graphs into trees

DOI10.1007/s43037-024-00373-7MaRDI QIDQ6613290

Garrett Tresch, Thomas Schlumprecht

Publication date: 2 October 2024

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

zbMATH Keywords

distortiontreesslashpowersstochastic embeddings

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• A framework for solving VLSI graph layout problems
• Coarse differentiation and multi-flows in planar graphs
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• 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
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A tight bound on approximating arbitrary metrics by tree metrics
• Stochastic approximation of lamplighter metrics
• Wasserstein distance and metric trees

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