A treehouse with custom windows: minimum distortion embeddings into bounded treewidth graphs

DOI10.1137/1.9781611974782.46MaRDI QIDQ4575784zbMATH OpenOpenAlexFDO

Authors Amir Nayyeri, Benjamin Raichel

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.46

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Metric spaces, metrizability (54E35)

Recommendations

• Viewing the rings of a tree: minimum distortion embeddings into trees
• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
• Approximation algorithms for embedding general metrics into trees
• Distortion Is Fixed Parameter Tractable
• Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs

Cited in

(9)

• scientific article; zbMATH DE number 7559245 (Why is no real title available?)
• Metric embedding via shortest path decompositions
• Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems
• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
• Viewing the rings of a tree: minimum distortion embeddings into trees
• scientific article; zbMATH DE number 7758347 (Why is no real title available?)
• Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
• Light Euclidean Spanners with Steiner Points
• FPT algorithms for embedding into low complexity graphic metrics

This page was built for publication: A treehouse with custom windows: minimum distortion embeddings into bounded treewidth graphs

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