Pathwidth, trees, and random embeddings

DOI10.1007/s00493-013-2685-8zbMath1349.05091arXiv0910.1409OpenAlexW2015577846MaRDI QIDQ2439830

James R. Lee, Anastasios Sidiropoulos

Publication date: 17 March 2014

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.1409

zbMATH Keywords

random treesshortest-path metric

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Flows in graphs (05C21)

Related Items

Metric Embedding via Shortest Path Decompositions ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ Stochastic approximation of lamplighter metrics ⋮ A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Coarse differentiation and multi-flows in planar graphs
• Graph minors. I. Excluding a forest
• Multicommodity flows in planar graphs
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• The geometry of graphs and some of its algorithmic applications
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Maximal Flow Through a Network
• Graph minor theory
• Approximating Sparsest Cut in Graphs of Bounded Treewidth
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• On the geometry of graphs with a forbidden minor
• Algorithms – ESA 2004
• Embedding k-Outerplanar Graphs into l1
• A tight bound on approximating arbitrary metrics by tree metrics