Hardness and approximation of minimum distortion embeddings

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

zbMATH Keywords

computational complexityapproximationdistortion

Mathematics Subject Classification ID

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