Hardness and approximation of minimum distortion embeddings
From MaRDI portal
Publication:991793
DOI10.1016/j.ipl.2010.02.009zbMath1209.68372OpenAlexW2074506096MaRDI QIDQ991793
Daniel Meister, Pinar Heggernes
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
Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (4)
On the Minimum Eccentricity Shortest Path Problem ⋮ On the minimum eccentricity shortest path problem ⋮ Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs ⋮ Line-distortion, bandwidth and path-length of a graph
Cites Work
- An optimal greedy heuristic to color interval graphs
- Restrictions of minimum spanner problems
- Linear discrepancy and bandwidth
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Domination on Cocomparability Graphs
- Computing the Bandwidth of Interval Graphs
- Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
- Low distortion maps between point sets
- Graph Classes: A Survey
- An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
- Approximating the bandwidth for asteroidal triple-free graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Hardness and approximation of minimum distortion embeddings