ridm@nrct.go.th   ระบบคลังข้อมูลงานวิจัยไทย   รายการโปรดที่คุณเลือกไว้

The non-uniform Bounded Degree Minimum Diameter Spanning Tree problem with an application in P2P networking

หน่วยงาน มหาวิทยาลัยเชียงใหม่

รายละเอียด

ชื่อเรื่อง : The non-uniform Bounded Degree Minimum Diameter Spanning Tree problem with an application in P2P networking
นักวิจัย : Chawachat,J. , Fakcharoenphol,J. , Jindaluang,W.
คำค้น : Computer Science Applications , Information Systems , Signal Processing , Theoretical Computer Science
หน่วยงาน : มหาวิทยาลัยเชียงใหม่
ผู้ร่วมงาน : -
ปีพิมพ์ : 2555
อ้างอิง : 00200190 , 2-s2.0-84865840326 , 10.1016/j.ipl.2012.08.015 , http://www.scopus.com/inward/record.url?partnerID=HzOxMe3b&scp=84865840326&origin=inward , http://cmuir.cmu.ac.th/handle/6653943832/38638
ที่มา : -
ความเชี่ยวชาญ : -
ความสัมพันธ์ : -
ขอบเขตของเนื้อหา : -
บทคัดย่อ/คำอธิบาย :

This paper considers the Bounded Degree Minimum Diameter Spanning Tree problem (BDST problem) with non-uniform degree bounds. In this problem, we are given a metric length function ℓ over a set V of n nodes and a degree bound B v for each v∈V, and want to find a spanning tree with minimum diameter such that each node v has degree at most B v. We present a simple extension of an O(logn)-approximation algorithm for this problem with uniform degree bounds of Könemann, Levin, and Sinha [J. Könemann, A. Levin, A. Sinha, Approximating the degree-bounded minimum diameter spanning tree problem, in: Algorithmica, Springer, 2003, pp. 109-121] to work with non-uniform degree bounds. We also show that this problem has an application in the peer-to-peer content distribution. More specifically, the Minimum Delay Mesh problem (MDM problem) introduced by Ren, Li and Chan [D. Ren, Y.-T. Li, S.-H. Chan, On reducing mesh delay for peer-to-peer live streaming, in: INFOCOM, 2008, pp. 1058-1066] under a natural assumption can be reduced to this non-uniform case of the BDST problem. © 2012 Elsevier B.V. All rights reserved.

บรรณานุกรม :
Chawachat,J. , Fakcharoenphol,J. , Jindaluang,W. . (2555). The non-uniform Bounded Degree Minimum Diameter Spanning Tree problem with an application in P2P networking.
    เชียงใหม่ : มหาวิทยาลัยเชียงใหม่ .
Chawachat,J. , Fakcharoenphol,J. , Jindaluang,W. . 2555. "The non-uniform Bounded Degree Minimum Diameter Spanning Tree problem with an application in P2P networking".
    เชียงใหม่ : มหาวิทยาลัยเชียงใหม่ .
Chawachat,J. , Fakcharoenphol,J. , Jindaluang,W. . "The non-uniform Bounded Degree Minimum Diameter Spanning Tree problem with an application in P2P networking."
    เชียงใหม่ : มหาวิทยาลัยเชียงใหม่ , 2555. Print.
Chawachat,J. , Fakcharoenphol,J. , Jindaluang,W. . The non-uniform Bounded Degree Minimum Diameter Spanning Tree problem with an application in P2P networking. เชียงใหม่ : มหาวิทยาลัยเชียงใหม่ ; 2555.