CENTER
Carnegie
Mellon School
of Computer Science|
Abstracts
|
The Joint ALADDIN/Theory/Operations Research Seminar |
|||||||||||||||||||||||||||||
|
L1 Embedding for Low Bandwidth Graphs Adam Meyerson
Abstract We introduce the first embedding of graphs of low bandwidth into L1, with distortion depending only upon the bandwidth. We extend this result to a new graph parameter called tree-bandwidth, which is very similar to (but more restrictive than) treewidth. This represents the first constant distortion embedding of a non-planar class of graphs into L1. Our results make use of a new technique that we call iterative embedding in which we define coordinates for a small number of points at a time. This is joint work with Douglas E. Carroll and Ashish Goel. |
|||||||||||||||||||||||||||||
 |
This material is based upon work
supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation |
Aladdin
