Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
DOI10.4230/LIPICS.SOCG.2018.21zbMATH Open1489.68345arXiv1712.06747MaRDI QIDQ5115789FDOQ5115789
Authors: Timothy Carpenter, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Anastasios Sidiropoulos 
Publication date: 18 August 2020
Full work available at URL: https://arxiv.org/abs/1712.06747
Recommendations
- Distortion Is Fixed Parameter Tractable
- Distortion is fixed parameter tractable
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Low-distortion embeddings of general metrics into the line
approximation algorithmsmetric embeddingsfixed-parameter tractable algorithms1-dimensional simplicial complexminimum-distortion embeddings
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Distance in graphs (05C12) Parameterized complexity, tractability and kernelization (68Q27) Metric embeddings as related to computational problems and algorithms (68R12)
Cites Work
- The geometry of graphs and some of its algorithmic applications
- Expander flows, geometric embeddings and graph partitioning
- The complexity of low-distortion embeddings between point sets
- Stable distributions, pseudorandom generators, embeddings, and data stream computation
- Title not available (Why is that?)
- Euclidean distortion and the sparsest cut
- Title not available (Why is that?)
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Distortion Is Fixed Parameter Tractable
- Title not available (Why is that?)
- Low-distortion embeddings of general metrics into the line
- Approximation algorithms for embedding general metrics into trees
- Distortion is fixed parameter tractable
- Hardness of Embedding Metric Spaces of Equal Size
- Low distortion maps between point sets
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Low Distortion Maps Between Point Sets
- Improved algorithms for optimal embeddings
- Fat polygonal partitions with applications to visualization and embeddings
- Inapproximability for metric embeddings into $\mathbb{R}^{d}$
- Inapproximability for planar embedding problems
- A robust model for finding optimal evolutionary trees
- A treehouse with custom windows: minimum distortion embeddings into bounded treewidth graphs
Cited In (21)
- Hardness and approximation of minimum distortion embeddings
- Bypassing the embedding
- Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
- Metric embedding via shortest path decompositions
- An exact algorithm for minimum distortion embedding
- An exact algorithm for minimum distortion embedding
- Distortion is fixed parameter tractable
- Random embeddings with an almost Gaussian distortion
- Title not available (Why is that?)
- A treehouse with custom windows: minimum distortion embeddings into bounded treewidth graphs
- Title not available (Why is that?)
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Distortion Is Fixed Parameter Tractable
- Light Euclidean Spanners with Steiner Points
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
- \(\ell _{1}\)-embeddability of 2-dimensional \(\ell _{1}\)-rigid periodic graphs
- FPT algorithms for embedding into low complexity graphic metrics
- Line-distortion, bandwidth and path-length of a graph
- Line-distortion, bandwidth and path-length of a graph
- Improved algorithms for optimal embeddings
This page was built for publication: Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115789)
