จักริน ชวชาติ

ประวัติ

ชื่อ: จักริน ชวชาติ

หัวข้องานวิจัย

Degree Limiting Minimum Diameter Tree Problem

เป็นปัญหา Network design มีกราฟ $G=(V,E)$ ต้องการหา spanning tree $T$ โดยมี objective ที่สนใจอยู่ 2 อย่าง ได้แก่ low diameter และ degree ของแต่ละ nodeไม่เกินดีกรีที่ node นั้นรับได้ ปัญหานี้สามารถนำไปประยุกต์ใช้เกี่ยวกับงาน peer to peer streaming ได้คือต้องการให้มี delay น้อย(สัมพันธ์กับ diameter) และการ assign งานไม่เกินที่แต่ละ node รับได้(สอดคล้องกับ degree)

Problem Definition

Given a metric length function $\ell$ over a set $V$ of $n$ nodes, and a degree-bound $B_{v}$ for each $v\in V$, the Degree-Limiting Minimum-Diameter Spanning Tree Problem (DLDST) is to find a spanning tree $T$ of $G$ of minimum diameter such that each node $v$ has degree at most $B_{v}$ in $T$.

เอกสารอ้างอิง

Sherlia Y. Shi and Jonathan S. Turner and Marcel Waldvogel. Dimensioning Server Access Bandwidth and Multicast Routing in Overlay Networks. In 11th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV’01),2001.