  Document Type  :  Latin Dissertation  Language of Document  :  English  Record Number  :  54296  Doc. No  :  TL24250  Call number  :  NR31920  Main Entry  :  Mohammad Ali Safari  Title & Author  :  D width, metric embedding, and their connectionsMohammad Ali Safari  College  :  The University of British Columbia (Canada)  Date  :  2007  Degree  :  Ph.D.  student score  :  2007  Page No  :  113  Abstract  :  Embedding between metric spaces is a very powerful algorithmic tool and has been used for finding good approximation algorithms for several problems. In particular, embedding to an l1 norm has been used as the key step in an approximation algorithm for the sparsest cut problem. The sparsest cut problem, in turn, is the main ingredient of many algorithms that have a divide and conquer nature and are used in various fields. While every metric is embeddable into l1 with distortion O(log n) [13], and the bound is tight [39], for special classes of metrics better bounds exist. Shortest path metrics for trees and outerplanar graphs are isometrically embeddable into l 1 [41], Seriesparallel graphs [28] and kouterplanar graphs [19] (for constant k) are embeddable intol 1 with constant distortion planar graphs and bounded treewidth graphs are conjectured to have constant distortion in embedding to l1. Bounded treewidth graphs are one of most general graph classes on which several hard problems are tractable. We study the embedding of seriesparallel graphs (or, more generally, graphs with treewidth two) into l1 and also the embedding between two line metrics. We then move our attention to the generalization of treewidth to digraphs and hypergraphs and study several relevant problems.  Subject  :  Applied sciences; Approximation algorithms; Dwidth; Metric embedding; Sparsest cut problem; Treewidth graphs; Computer science; 0984:Computer science  Added Entry  :  The University of British Columbia (Canada) 
     
   
http://lib.clisel.com/site/catalogue/54296

 