This page uses JavaScript and requires a JavaScript enabled browser.Your browser is not JavaScript enabled.
مرکز و کتابخانه مطالعات اسلامی به زبان های اروپایی
منو
درگاههای جستجو
مدارک
جستجوی پیشرفته
مرور
جستجو در سایر کتابخانه ها
مستندات
جستجوی پیشرفته
مرور
منابع دیجیتال
تمام متن
اصطلاحنامه
درختواره
پرسش و پاسخ
سوالات متداول
پرسش از کتابدار
پیگیری پرسش
ورود
ثبت نام
راهنما
خطا
رکورد قبلی
رکورد بعدی
"
D -width, metric embedding, and their connections
"
Mohammad Ali Safari
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 connections\ Mohammad 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], Series-parallel graphs [28] and k-outerplanar graphs [19] (for constant k) are embeddable intol 1 with constant distortion planar graphs and bounded tree-width graphs are conjectured to have constant distortion in embedding to l1. Bounded tree-width graphs are one of most general graph classes on which several hard problems are tractable. We study the embedding of series-parallel graphs (or, more generally, graphs with tree-width two) into l1 and also the embedding between two line metrics. We then move our attention to the generalization of tree-width to digraphs and hypergraphs and study several relevant problems.
Subject
:
Applied sciences; Approximation algorithms; D-width; Metric embedding; Sparsest cut problem; Tree-width graphs; Computer science; 0984:Computer science
Added Entry
:
The University of British Columbia (Canada)
https://lib.clisel.com/site/catalogue/54296
کپی لینک
پیشنهاد خرید
پیوستها
عنوان :
نام فایل :
نوع عام محتوا :
نوع ماده :
فرمت :
سایز :
عرض :
طول :
NR31920_12247.pdf
NR31920.pdf
پایان نامه لاتین
متن
application/octet-stream
2.99 MB
85
85
نمایش
نظرسنجی
نظرسنجی منابع دیجیتال
1 - آیا از کیفیت منابع دیجیتال راضی هستید؟
X
کم
متوسط
زیاد
ذخیره
پاک کن