Hardness and approximation of minimum distortion embeddings

DOI10.1016/J.IPL.2010.02.009MaRDI QIDQ991793zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1696538 (Why is no real title available?)
• scientific article; zbMATH DE number 1186230 (Why is no real title available?)
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• An optimal greedy heuristic to color interval graphs
• Approximating the bandwidth for asteroidal triple-free graphs
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Computing the Bandwidth of Interval Graphs
• Domination on Cocomparability Graphs
• Graph Classes: A Survey
• Linear discrepancy and bandwidth
• Low distortion maps between point sets
• Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Restrictions of minimum spanner problems

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
• Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
• Inapproximability for planar embedding problems
• 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)