Approximating the bandwidth via volume respecting embeddings
type: Item
instance of: scholarly article
title: Approximating the bandwidth via volume respecting embeddings
zbMATH Open document ID: 0958.68191
published in: Journal of Computer and System Sciences
publication date: 2000-08-27T00:00:00Z
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1497375
zbMATH Keywords: volume respecting embeddings
zbMATH Keywords: small distortion embeddings
MaRDI profile type: Publication
OpenAlex ID: W2080608361
cites work: The Bandwidth of Caterpillars with Hairs of Length 1 and 2
cites work: Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
cites work: Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
cites work: On Lipschitz embedding of finite metric spaces in Hilbert space
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Graphs with small bandwidth and cutwidth
cites work: The bandwidth problem and operations on graphs
cites work: The Johnson-Lindenstrauss lemma and the sphericity of some graphs
cites work: Complexity Results for Bandwidth Minimization
cites work: Q3664299
cites work: Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
cites work: Bandwidth Minimization: An approximation algorithm for caterpillars
cites work: Computing the Bandwidth of Interval Graphs
cites work: Approximating the bandwidth for asteroidal triple-free graphs
cites work: Q3935355
cites work: Q3751649
cites work: Q4871767
cites work: The geometry of graphs and some of its algorithmic applications
cites work: Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
cites work: The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
cites work: The NP-completeness of the bandwidth minimization problem
cites work: Q5845761
cites work: Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
cites work: On the Probable Performance of Heuristics for Bandwidth Minimization
DOI: 10.1006/JCSS.1999.1682
author: Uriel Feige
description: scientific article; zbMATH DE number 1497375