Hardness and approximation of minimum distortion embeddings
type: Item
instance of: scholarly article
title: Hardness and approximation of minimum distortion embeddings
zbMATH Open document ID: 1209.68372
author: Pinar Heggernes
author: Daniel Meister
published in: Information Processing Letters
publication date: 2010-09-07T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5780824
zbMATH Keywords: distortion
zbMATH Keywords: computational complexity
zbMATH Keywords: approximation
MaRDI profile type: Publication
full work available at URL: j.ipl.2010.02.009
OpenAlex ID: W2074506096
cites work: Approximation algorithms for low-distortion embeddings into low-dimensional spaces
cites work: Graph Classes: A Survey
cites work: Linear discrepancy and bandwidth
cites work: Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs
cites work: Low distortion maps between point sets
cites work: Computing the Bandwidth of Interval Graphs
cites work: Approximating the bandwidth for asteroidal triple-free graphs
cites work: Q2766686
cites work: Domination on Cocomparability Graphs
cites work: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
cites work: An optimal greedy heuristic to color interval graphs
cites work: An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
cites work: Restrictions of minimum spanner problems
cites work: Q3839788
DOI: 10.1016/J.IPL.2010.02.009
description: scientific article; zbMATH DE number 5780824