Hardness and approximation of minimum distortion embeddings
From MaRDI portal
Publication:991793
DOI10.1016/J.IPL.2010.02.009zbMATH Open1209.68372OpenAlexW2074506096MaRDI QIDQ991793FDOQ991793
Authors: Pinar Heggernes, Daniel Meister 
Publication date: 7 September 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2010.02.009
Recommendations
- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
- Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
- Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
- Automata, Languages and Programming
- Inapproximability for planar embedding problems
Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Graph Classes: A Survey
- Domination on Cocomparability Graphs
- Computing the Bandwidth of Interval Graphs
- An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
- An optimal greedy heuristic to color interval graphs
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Title not available (Why is that?)
- Linear discrepancy and bandwidth
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Low distortion maps between point sets
- Restrictions of minimum spanner problems
- Title not available (Why is that?)
- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
- Approximating the bandwidth for asteroidal triple-free graphs
Cited In (10)
- On the minimum eccentricity shortest path problem
- Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
- Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics
- Automata, Languages and Programming
- On the minimum eccentricity shortest path problem
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Inapproximability for planar embedding problems
- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Line-distortion, bandwidth and path-length of a graph
This page was built for publication: Hardness and approximation of minimum distortion embeddings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991793)
