Hardness and approximation of minimum distortion embeddings

DOI10.1016/j.ipl.2010.02.009zbMath1209.68372MaRDI 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 complexity; approximation; distortion

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Line-distortion, bandwidth and path-length of a graph, Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs, On the minimum eccentricity shortest path problem, On the Minimum Eccentricity Shortest Path Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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