Approximating the bandwidth via volume respecting embeddings
From MaRDI portal
Publication:1577009
DOI10.1006/JCSS.1999.1682zbMATH Open0958.68191OpenAlexW2080608361MaRDI QIDQ1577009FDOQ1577009
Authors: Uriel Feige 
Publication date: 27 August 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/6d39860116554a6c08506553db7e2d93efe3e040
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
- The geometry of graphs and some of its algorithmic applications
- Title not available (Why is that?)
- Title not available (Why is that?)
- The NP-completeness of the bandwidth minimization problem
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- Computing the Bandwidth of Interval Graphs
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- Complexity Results for Bandwidth Minimization
- On Lipschitz embedding of finite metric spaces in Hilbert space
- The bandwidth problem for graphs and matrices—a survey
- Graphs with small bandwidth and cutwidth
- The Johnson-Lindenstrauss lemma and the sphericity of some graphs
- The bandwidth problem and operations on graphs
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Bandwidth Minimization: An approximation algorithm for caterpillars
- On the Probable Performance of Heuristics for Bandwidth Minimization
- Approximating the bandwidth for asteroidal triple-free graphs
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
- Title not available (Why is that?)
Cited In (33)
- Improved bandwidth approximation for trees and chordal graphs
- An exponential time 2-approximation algorithm for bandwidth
- An exponential time 2-approximation algorithm for bandwidth
- The legacy of Jean Bourgain in geometric functional analysis
- Hardness results for approximating the bandwidth
- Retracting Graphs to Cycles
- Faster Exact Bandwidth
- Approximating bandwidth by mixing layouts of interval graphs
- Volume distortion for subsets of Euclidean spaces
- Convex relaxations for permutation problems
- Limitations to Fréchet's metric embedding method
- On the 3-distortion of a path
- Labeling schemes for weighted dynamic trees
- Optimal distortion embedding of complete binary trees into lines
- Graph bandwidth of weighted caterpillars
- Mapping \(n\) grid points onto a square forces an arbitrarily large Lipschitz constant
- Interval degree and bandwidth of a graph
- On multiplicative \(\lambda\)-approximations and some geometric applications
- Approximating the bandwidth of caterpillars
- Algorithms for graphs with small octopus
- The intrinsic dimensionality of graphs
- Volume in general metric spaces
- Cellular resolutions of cointerval ideals
- On the graph turnpike problem
- Delone sets that are not rectifiable under Lipschitz co-uniformly continuous bijections
- Compact representation of graphs with bounded bandwidth or treedepth
- Combinatorial theorems about embedding trees on the real line
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- Complexity and Algorithms for Well-Structured k-SAT Instances
- Moderately exponential time and fixed parameter approximation algorithms
- Title not available (Why is that?)
- Line-distortion, bandwidth and path-length of a graph
- Title not available (Why is that?)
This page was built for publication: Approximating the bandwidth via volume respecting embeddings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1577009)
